1
$\begingroup$

Consider the following scheme:

  1. Perform an (N,N) Reed-Solomon encoding (i.e. N data blocks, N parity blocks)
  2. Drop the N data blocks and keep only the N parity blocks.

Are these N parity blocks an all-or-nothing transform? (meaning missing even one parity block does not permit decoding the original data blocks)

Improve this question
$\endgroup$
1
  • $\begingroup$ does my answer address your question? $\endgroup$ – kodlu May 23 '19 at 22:24
1
$\begingroup$

Reed-Solomon codes are Maximum-Distance-Separable codes and thus have the property that in a $[n,k]$ RS code ---- meaning than there are a total of $n$ blocks of which $k$ are data blocks and $n-k$ are parity block ($n=2N$ and $k=N$ in the OP's notation) ---- any $k$ blocks are sufficient to reconstruct the entire codeword, that is, all the blocks can be found if we know $k$ of them. Note that it does not matter whether the $k$ blocks available are a mixture of data and parity blocks or parity blocks only, just as long as $k$ blocks are available.

So, in the scheme envisioned by the OP, if one has a $[2N,N]$ Reed-Solomon code ($N$ data blocks, $N$ parity blocks, for a total of $2N$ blocks) and keeps only the $N$ parity blocks, the $N$ data blocks can be reconstructed. If fewer than $N$ of the parity blocks, then the data blocks cannot be reconstructed in the sense that the decoder can come up with a list of $M$ possible candidates for the $N$ data blocks but cannot say which of the candidates is the correct one. Here, each of the $M$ candidates on the list is a vector $[D_1, D_2, \ldots, D_N]$ of $N$ data block (each $D_i$ is a data block) and the decoder cannot determine which is the correct vector of $N$ data blocks. What is $M$? Well, $M$ is the number of possible distinct values that each data block might have and thus is either the number of elements in the finite field over which the Reed-Solomon code is defined, or some power $L$ thereof if each data block is a vector of length $L$ over the finite field (and we are using an interleaved Reed-Solomon code). Either way, $M$ is pretty large.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you @dilip, the answer is clear. As a side question, imagine that I want to add an extra constraint to my problem : "The $N$ data blocks should be reconstructed exclusively from the $N$ parity blocks, and not from a mixture of data and parity blocks". Would Reed-Solomon (non-systematic?) still be a candidate for this constrained scheme? $\endgroup$ – stefanix May 26 '19 at 7:09
  • $\begingroup$ @stefanix As I said in my answer, it does not matter to the general (erasures-correcting) decoding algorithm whether the $N$ available blocks are parity blocks only or a mixture of data and parity blocks. But it is certainly possible to modify the general algorithm to tell it to refuse to decode a mixture of data and parity blocks, and decode iff $N$ parity blocks are available. Similarly, when $<N$ blocks are available, the standard RS decoder fails to decode (gives error signal only), and it is necessary to re-program it to spit out the list of $M$ possible vectors of data blocks instead. $\endgroup$ – Dilip Sarwate May 27 '19 at 2:37
0
$\begingroup$

A Reed-Solomon code is an MDS code over the symbol alphabet $\mathbb{F}_q,$ with parameters $[n,k,n-k+1]$. Here, the length $n=2N$ the dimension $k=N$ and the minimum distance is $d=N+1.$

Such codes form Orthogonal Arrays of strength $t=n-d+1=N+1.$

And an OA of strength $t$ is also an OA of strength $t'\leq t.$ Take $t'=N.$ Thus, yes, dropping one of the $N$ parity blocks would result in an AONT, leaking no information about the missing block.

Edit: In general any $N$ blocks are enough to reconstruct the missing blocks.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Just to make sure: dropping one of the N parity blocks does not leak any information on any of the N data blocks? $\endgroup$ – stefanix May 22 '19 at 15:24
  • $\begingroup$ So how many blocks do you need in total to reconstruct the data? $\endgroup$ – stefanix May 24 '19 at 8:56
  • $\begingroup$ My comment above is in error, I will edit the body of the paper, to stop the confusion. $\endgroup$ – kodlu May 24 '19 at 22:27
  • $\begingroup$ Your last paragraph is incorrect even after the edit. $\endgroup$ – Dilip Sarwate May 25 '19 at 14:53
  • $\begingroup$ OK, much better after the second edit. $\endgroup$ – Dilip Sarwate May 27 '19 at 2:26

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.