1
$\begingroup$

I would like to know, since I am not that knowledgeable in this subject, if this idea is feasible or widely implemented:

If a data package is sent, I know parity-bytes are used to detect errors. Could we not use a similar concept to self-complete data packages? Let's say a client requests an image to be sent from a server. The server first sents a function of each row and column, e.g. the sum of all pixel values in each row and column, so 20 values for a 10x10 image. The server then sends the values of exactly as many pixels as are needed to let only one possible combination of all pixel values remain.

Would this require less or more data packages to be sent, in the best/average/worst case?

$\endgroup$
  • $\begingroup$ In some way, this is what all compression algorithms do: look for redundancy in the data, and take it away. JPG, for instance, does something similar to what you describe, where the "function" is the DCT, and only the coefficients are stored/transmitted. $\endgroup$ – MBaz Sep 28 at 14:35
  • $\begingroup$ What you describe sounds more or less like error correcting codes - Reed-Solomon error correction is one example $\endgroup$ – tonys Sep 28 at 20:22
1
$\begingroup$

What you are suggesting is indeed rooted on concepts that are important in DSP:

  • On the channel coding side, you have for instance error correction codes (or error correcting codes, both ECC)

  • On the source coding side, since you mention Sudoku, techniques like matrix completion, sparse sampling or compressive sensing are possibilities to approximately recover incomplete grids.

However, they work on assumptions on data like positivity, sparsity), and approximate recovery. I have not seen yet such a scheme working for universal lossless compression. An argument is derived from the Dirichlet or pigeonhole principle, another one is easier with recursion. Suppose you have a clever scheme that self-completes data packages, based on some functions that combine inputs. For compression, you expect that it turns all $B$ bit-stored file on a smaller number of bits, say $B-1$ bits or ledd. Then you could apply it again, and again, until you reach $0$ bits, which does not make sense.

So, this does not appear possible, unless you have additional assumptions that could reduce the space of possible data.

$\endgroup$
0
$\begingroup$

Say each of the 10 pixel values on a row consists of $N$ bits. An $N$-bit wrap-around-arithmetic sum of the values gives just enough additional information to reconstruct the 10th value from the 9 previous values: subtract the 9-sum from the 10-sum. So 10 values that are needed for reconstruction each row, which is the same as the size of the original data.

To summarize, the data size stays the same. If raw data is sent in the packages, the number of needed data packages will stay the same. If further data compression is performed, the situation will need to be reassessed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.