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

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&#4294967295;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