Forums

Complexity of reed-solomon (n, k) over m-bit symbol field

Started by sheaurutong October 28, 2010
I am trying to learn RS deeper. For the most conventional RS(n,k) defined
for a m-bit symbol field , we let n=2^m to maximize the codeword block
size. Its decoding complexity is known to be O(n log^2 n). But if we let n
to be independent of m, then what will be the decoding complexity? 


On Oct 28, 7:23�am, "sheaurutong"
<srtong@n_o_s_p_a_m.mail.npust.edu.tw> wrote:
> I am trying to learn RS deeper. For the most conventional RS(n,k) defined > for a m-bit symbol field , we let n=2^m to maximize the codeword block > size. Its decoding complexity is known to be O(n log^2 n). But if we let n > to be independent of m, then what will be the decoding complexity?
The decoding complexity is O(n log^2 n) finite-field operations (i.e. with m-bit operands). And n can be **at most** 2^m (or 1 + 2^m in one special case that will be ignored in what follows). So, even when n is "independent" of m, n can only have values between k and 2^m, and the decoding complexity is still O(n log^2 n) finite-field operations; except if n = k in which case the decoding complexity is 0 (or O(1) if you prefer fancy notation) because no decoding needs to be done: the channel output is accepted as is to be the transmitted data. No practical decoder uses the calculation methods that underlie the claim of O(n log^2 n) complexity for decoding RS codes. It should be viewed as an asymptotic result that will never be approached in our lifetime. --Dilip Sarwate
dvsarwate  <dvsarwate@yahoo.com> wrote:

>No practical decoder uses the calculation methods >that underlie the claim of O(n log^2 n) complexity >for decoding RS codes. It should be viewed as an >asymptotic result that will never be approached in >our lifetime.
That's right. In most cases a RS decoder has a computational component per codeword that is order r^2, and a component that is n*r. (n is the total length of the codeword, r is the number of check symbols) If you want to view these on a per decoded bit basis (rather than per codeword), they become r^2 / (n*m) and r/m respectively. There are usually the more realistic metrics, as they indicate the amount of hardware needed for a given throughput. Steve

sheaurutong wrote:

> I am trying to learn RS deeper. For the most conventional RS(n,k) defined > for a m-bit symbol field , we let n=2^m to maximize the codeword block > size.
You *can* select n and get *a* code. But isn't it by definition of the Reed Solomon code that n = 2^m - 1 ?
> Its decoding complexity is known to be O(n log^2 n). But if we let n > to be independent of m, then what will be the decoding complexity?
For algebraic decoding of a nontrivial linear code the complexity can't be better then n log(n). Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
On Oct 28, 10:51&#2013266080;am, Vladimir Vassilevsky <nos...@nowhere.com> asked:

> isn't it by definition of the > Reed Solomon code that n = 2^m - 1 ?
Not necessarily, according to the original paper by Reed and Solomon which merely required that n be no larger than the size of the field (which was not restricted to being 2^m, but could be p^m for arbitrary prime p and positive integer m). The formulation by Reed and Solomon did not require the codes to be cyclic either, though most current implementations use cyclic (or shortened or extended forms of cyclic) Reed-Solomon codes. Dilip Original Intent