Forums

Reed-Solomon code block size choice

Started by mguo May 11, 2006
Hi all, In designing a reed-solomon code, one has to choose the appropriate
code size. If the constraint is computational complexity and delay, is it
better to use a large block size, or use several numbers of small blocks?
In other words, for RS(n,k), is it computationally more efficient to have
n=255, or divide data into 17 blocks with each one has n=15? Here we
assume other factors like error correcting capability doesn't matter. 

Thanks a lot.
-Min
"mguo" <mguo@omnexcontrols.com> asked in message 
news:CPWdnf7-Z5cY9_7ZnZ2dnUVZ_tudnZ2d@giganews.com...
> Hi all, In designing a reed-solomon code, one has to choose the > appropriate > code size. If the constraint is computational complexity and delay, is it > better to use a large block size, or use several numbers of small blocks? > In other words, for RS(n,k), is it computationally more efficient to have > n=255, or divide data into 17 blocks with each one has n=15? Here we > assume other factors like error correcting capability doesn't matter.
Let t = (n-k)/2 denote the error-correcting capability of the Reed-Solomon code. Then, syndrome generation uses 2t multipliers and storage locations, the key equation solver uses 6t multipliers and storage locations, and the Chien search/error correction circuit has 2t+2 multipliers and storage locations. In addition, 2n locations are required to store (two) codewords while they are being processed. The latency (time between first codeword input symbol and last decoder output symbol) is 3n clock cycles. Based on this and your assertion that error correcting capability does not matter to you, you should feel free to arrive at the conclusion that 17 blocks of (15,k/17) codes is obviously preferable over a (255, k) code. Others, more concerned about error correction, may feel that using 17 blocks from a (15, 14) code is NOT preferable to a (255, 238) code. The latter can correct 8 errors, the former can only *detect*, NOT correct, one error in each block, and thus as many as 17 single errors in 255 symbols, provided no more than one symbol is in error in each 15-symbol codeword. YMMV.
> >"mguo" <mguo@omnexcontrols.com> asked in message >news:CPWdnf7-Z5cY9_7ZnZ2dnUVZ_tudnZ2d@giganews.com... >> Hi all, In designing a reed-solomon code, one has to choose the >> appropriate >> code size. If the constraint is computational complexity and delay, is
it
>> better to use a large block size, or use several numbers of small
blocks?
>> In other words, for RS(n,k), is it computationally more efficient to
have
>> n=255, or divide data into 17 blocks with each one has n=15? Here we >> assume other factors like error correcting capability doesn't matter. > >Let t = (n-k)/2 denote the error-correcting capability of the >Reed-Solomon code. Then, syndrome generation uses >2t multipliers and storage locations, the key equation solver >uses 6t multipliers and storage locations, and the Chien >search/error correction circuit has 2t+2 multipliers and storage >locations. In addition, 2n locations are required to store (two) >codewords while they are being processed. The latency >(time between first codeword input symbol and last decoder >output symbol) is 3n clock cycles. Based on this and your >assertion that error correcting capability does not matter to >you, you should feel free to arrive at the conclusion that >17 blocks of (15,k/17) codes is obviously preferable over >a (255, k) code. Others, more concerned about error >correction, may feel that using 17 blocks from a (15, 14) >code is NOT preferable to a (255, 238) code. The >latter can correct 8 errors, the former can only *detect*, >NOT correct, one error in each block, and thus as many >as 17 single errors in 255 symbols, provided no more >than one symbol is in error in each 15-symbol codeword. >YMMV. > > >
YMMV, Thanks a lot for your comment. If I have 17 RS(15,11) code, it will still be able to correct 2*4*17=138 bits error. I have not implemented this type of code on a general purpose DSP before, so not sure the computational complexity. What you said is an implementation on ASIC/FPGA or DSP processor? -Min
> >"mguo" <mguo@omnexcontrols.com> asked in message >news:CPWdnf7-Z5cY9_7ZnZ2dnUVZ_tudnZ2d@giganews.com... >> Hi all, In designing a reed-solomon code, one has to choose the >> appropriate >> code size. If the constraint is computational complexity and delay, is
it
>> better to use a large block size, or use several numbers of small
blocks?
>> In other words, for RS(n,k), is it computationally more efficient to
have
>> n=255, or divide data into 17 blocks with each one has n=15? Here we >> assume other factors like error correcting capability doesn't matter. > >Let t = (n-k)/2 denote the error-correcting capability of the >Reed-Solomon code. Then, syndrome generation uses >2t multipliers and storage locations, the key equation solver >uses 6t multipliers and storage locations, and the Chien >search/error correction circuit has 2t+2 multipliers and storage >locations. In addition, 2n locations are required to store (two) >codewords while they are being processed. The latency >(time between first codeword input symbol and last decoder >output symbol) is 3n clock cycles. Based on this and your >assertion that error correcting capability does not matter to >you, you should feel free to arrive at the conclusion that >17 blocks of (15,k/17) codes is obviously preferable over >a (255, k) code. Others, more concerned about error >correction, may feel that using 17 blocks from a (15, 14) >code is NOT preferable to a (255, 238) code. The >latter can correct 8 errors, the former can only *detect*, >NOT correct, one error in each block, and thus as many >as 17 single errors in 255 symbols, provided no more >than one symbol is in error in each 15-symbol codeword. >YMMV. > > >
YMMV, Thanks a lot for your comment. If I have 17 RS(15,11) code, it will still be able to correct 2*4*17=138 bits error. I have not implemented this type of code on a general purpose DSP before, so not sure the computational complexity. What you said is an implementation on ASIC/FPGA or DSP processor? -Min
On 2006-05-11, mguo <mguo@omnexcontrols.com> wrote:
> > Thanks a lot for your comment. If I have 17 RS(15,11) code, it will still > be able to correct 2*4*17=138 bits error.
Don't forget that each block can only correct errors within the block. If you use a wider code, your data will be more tolerant of bursts of errors. You can also follow your RS with a convolutional interleaver to spread the error correcting power around. -- Ben Jackson <ben@ben.com> http://www.ben.com/
"mguo" <mguo@omnexcontrols.com> wrote in message 
news:2NSdnd86eKYYF_7ZRVn-rw@giganews.com...

> Thanks a lot for your comment. If I have 17 RS(15,11) code, it will still > be able to correct 2*4*17=138 bits error.
Not quite. Your system corrects two symbols in each block, where you have implicitly assumed that the symbols are 4-bit elements of GF(16). But, this DOES NOT MEAN that *any* 8-bit error pattern within a block can be corrected. A burst of 6 bit errors can corrupt 3 symbols and the decoder will fail to decode. In fact, even just 3-bit error patterns such as 100101 can corrupt 3 symbols (where one symbol has an error of 0001, the next 0010, and the third 1000). Turning the other cheek, a (255, 187) RS code is an *enormously* powerful code that is probably far beyond the capabilities of a DSP processor unless the processor is working off-line and speed is not an issue.
>. What you said is an implementation on ASIC/FPGA or DSP > processor?
ASIC.
> >"mguo" <mguo@omnexcontrols.com> wrote in message >news:2NSdnd86eKYYF_7ZRVn-rw@giganews.com... > >> Thanks a lot for your comment. If I have 17 RS(15,11) code, it will
still
>> be able to correct 2*4*17=138 bits error. > >Not quite. Your system corrects two symbols in each block, >where you have implicitly assumed that the symbols are 4-bit >elements of GF(16). But, this DOES NOT MEAN that *any* >8-bit error pattern within a block can be corrected. A burst >of 6 bit errors can corrupt 3 symbols and the decoder will >fail to decode. In fact, even just 3-bit error patterns such as >100101 can corrupt 3 symbols (where one symbol has an >error of 0001, the next 0010, and the third 1000). >
Sorry forgot to mention that it will be followed by an interleaver so that a long burst error will be spread into multiple small blocks, resulting still contiguous errors in each block. Yes you are right, in each block 8bits error could obviously spread into 3 symbols instead of 2.
>Turning the other cheek, a (255, 187) RS code is an *enormously* >powerful code that is probably far beyond the capabilities of a >DSP processor unless the processor is working off-line and speed >is not an issue. >
Really? TI reported that a (208, 188) decoder can be implemnted with 2000 cycles with DSP software(C compiler). (255, 187) probably takes several times more computation. If that's true, it should be well within the capability of latest DSP processor as long as data rate does not go too high.
> >>. What you said is an implementation on ASIC/FPGA or DSP >> processor? > >ASIC. > > >