Re: [OctDev] Bchenco - Communication Toolbox

[David B. <Dav...@mo...>]

Marco Maso wrote:
> Il giorno Thu, 11 Sep 2008 09:24:01 +0200
> David Bateman <ad...@gm...> ha scritto:
>
>   
>> Marco Maso wrote:
>>     
>>> Hi everybody, my name is Marco and this is my first message to the
>>> ML. I've decided to subscribe because i have a little problem usign
>>> the bchenco function provided with the communications toolbox of
>>> octave-forge (versio 1.0.6). I'm currently using Octave 3.0.2. As i
>>> can read on the Function Reference page this function:
>>>
>>> "Encodes the message msg using a [n,k] BCH coding. The variable msg
>>> is a binary array with k columns and an arbitrary number of rows.
>>> Each row of msg represents a single symbol to be coded by the BCH
>>> coder. The coded message is returned in the binary array code
>>> containing n columns and the same number of rows as msg."
>>>
>>> And after:
>>>
>>> "By default the generator polynomial used in the BCH coding is
>>> based on the properties of the Galois Field GF(2^m). This default
>>> generator polynomial can be overridden by a polynomial in g.
>>> Suitable generator polynomials can be constructed with bchpoly."
>>>
>>> I'm developing a software that needs a BCH encoder with the
>>> following parameters (among the others...):
>>>
>>> - BCH uncoded word length = Kbch = 32208
>>> - BCH coded word length = Nbch = 32400
>>>
>>> - BCH uncoded word length = Kbch = 7302
>>> - BCH coded word length = Nbch = 7200
>>>
>>> In the first case i use a g polynomial obtained by multiplying 12
>>> polynomials of grade 16. This polynomial generator works correctly
>>> with the other 5 couples (n,k) i need to test on my simulator.
>>>
>>> In the second case In the first case i use a g polynomial obtained
>>> by multiplying 12 polynomials of grade 14. This polynomial
>>> generator works correctly with the other 6 couples (n,k) i need to
>>> test on my simulator.
>>>
>>> Obviously thes are not numbers invented by myself but i'm using a
>>> manual as a reference so i'm sure they are correct.
>>>
>>>
>>> In both cases i obtain this error:
>>>
>>> error: bchenco: can not find valid generator polynomial for
>>> parameters error: evaluating assignment expression near line 140,
>>> column 3
>>>
>>> I can't properly understand where the problem can be even because i
>>> can't find the source code of this function...
>>>
>>> Can anybody explain me why i receive such an error?
>>>
>>> Should i post the coefficients of my g polynomial?
>>>
>>> Last question (stupid) : when working with octave a polynomial
>>> insertion has always to be done from LSB to MSB am i right?
>>>
>>> Thanks a lot
>>>
>>> Marco  
>>>
>>>
>>>       
>> Could you supply a short example demonstrating this issue?
>>
>> D.
>>     
>
>
> Ok! So i give you some consistent data:
>
> I use this polynomial generator ( given from LSB to MSB, you don't
> have answered to that question so i believe this is correct):
>
>  Columns 1 through 20:
>
>    1   1   1   0   0   1   1   1   1   0   1   0   1   0   1   0   0
> 1   0   0
>
>  Columns 21 through 40:
>
>    0   0   0   0   0   1   1   0   0   1   1   0   1   1   1   0   1
> 1   1   1
>
>  Columns 41 through 60:
>
>    1   0   1   0   0   0   0   1   1   1   1   0   0   0   1   0   1
> 1   0   0
>
>  Columns 61 through 80:
>
>    0   0   0   0   1   0   0   1   0   0   0   1   0   0   0   1   0
> 0   0   0
>
>  Columns 81 through 100:
>
>    1   0   1   0   1   1   0   0   0   0   1   1   1   0   1   1   0
> 0   0   1
>
>  Columns 101 through 120:
>
>    1   0   1   1   0   0   1   1   0   1   0   0   1   1   1   1   0
> 0   1   1
>
>  Columns 121 through 140:
>
>    0   0   0   0   1   0   1   0   0   0   1   1   1   0   0   0   1
> 0   0   0
>
>  Columns 141 through 160:
>
>    1   0   1   0   0   0   1   1   1   0   1   0   0   0   1   0   0
> 0   0   1
>
>  Columns 161 through 180:
>
>    1   1   0   0   0   0   0   1   0   1   1   1   0   0   0   0   0
> 1   1   0
>
>  Columns 181 through 193:
>
>    0   1   0   0   0   1   1   1   0   0   1   0   1
>
>
> As you can see this polynomial has grade 192.
>
>
> I call this polynomial g, with this i try to generate the BCH code with
> this command:
>
> code = bchenco(ones(1, 32208), 32400, 32208, g);
>
> this gives:
>
> octave:140> e = bchenco(ones(1,32208),32400,32208,g);
> error: bchenco: can not find valid generator polynomial for parameters
> error: evaluating assignment expression near line 140, column 3
>
> Obviously the part "line 140" si referred to the octave prompt and
> change everytime i call this function
>
> I'm codifying a ones word but it's not important, i'm just testing.
>
> Another valid couple (n, k) i'm trying is (48600, 48408) and so:
>
> octave:145> code = bchenco(ones(1,48408),48600,48408,fliplr(g));
> octave:146> length(code)
> ans =  48600
>
> And this is the result with other 4 known couples, no problems at all.
>
> With another polynomial generator, let's call it g_1, i have other 7
> known couples to test, and i have a problem with only one couple her
> too:
>
> g_1 = 
>  
>  Columns 1 through 20:
>
>    1   0   1   0   0   1   0   1   1   0   1   0   0   0   0   0   1
> 0   0   1
>
>  Columns 21 through 40:
>
>    1   0   0   0   1   0   0   0   1   0   1   1   1   1   1   0   1
> 0   1   1
>
>  Columns 41 through 60:
>
>    1   1   1   0   0   1   1   1   1   1   1   1   0   0   0   1   0
> 1   0   0
>
>  Columns 61 through 80:
>
>    1   0   1   0   1   0   0   1   0   1   1   0   0   0   0   0   1
> 0   0   1
>
>  Columns 81 through 100:
>
>    1   1   0   0   0   1   0   1   1   1   0   0   0   1   0   0   1
> 0   1   1
>
>  Columns 101 through 120:
>
>    0   0   1   1   0   1   0   0   0   1   1   0   0   1   0   0   1
> 1   0   1
>
>  Columns 121 through 140:
>
>    1   0   0   1   0   1   1   0   0   0   0   1   1   0   0   1   0
> 1   0   1
>
>  Columns 141 through 160:
>
>    0   1   1   1   1   1   0   1   1   0   1   1   0   1   0   0   0
> 1   1   0
>
>  Columns 161 through 169:
>
>    0   0   0   0   0   0   1   0   1
>
>
>
> This polynomial has grade 168. Again:
>
> octave:148> code = bchenco(ones(1, 7032), 7200, 7032, g_1);
> error: bchenco: can not find valid generator polynomial for parameters
> error: evaluating assignment expression near line 148, column 3
>
>
> Another valid couple (n, k) i'm trying is (3072, 3240) and so:
>
> octave:148> code = bchenco(ones(1, 3072), 3240, 3072, g_1);
> octave:149> length(code)
> ans =  3240
>
>   
>

With the default primitive polynomial, there is no valid BCH code for 
your values of N and K. You need to either change N and K or try a 
different valid primitive polynomial. For example,

M = 13
N = 2^M - 1; % Next value of N above 7200
K = N - 168;
p = primpoly(13, 'all');
prim = NaN
for i = 1: length(p)
  try
     g = bchpoly(N, K, p(i))
     prim = p(i);
     break;
  catch
     continue
  end
end

this is rather slow but finds that there is in fact NO valid generator 
with any of the primitive polynomials of 2^13-1 and your values of N and 
K, and prim will end up being NaN. I'd suggest you change your value of 
K to N - 169 and then yes there is a valid BCH code that can be found. 
In particular the one given by

N = 2^13 - 1;
g = bchpoly(N, N - 169);

Note not all values of N abd K are valid for BCH codes.

D.