Reed-Solomon code block size choice

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. 
>
>
>