Forums

Reed-Solomon example in 802.16 standard

Started by mr April 14, 2005
Hi--

I'm having difficulty getting the same results as the Reed-Solomon encoded
test vectors provided in the 802.16 standard.  The systematic part is fine,
the problem is with the parity bits.  I'm using Matlab to simulate the RS
encoding (using rsenc).  Anybody has had a similar problem?  Any Matlab
source code available to generate the "right" codewords?  Thanks for your
help!



		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com
Hi there,


> I'm having difficulty getting the same results as the Reed-Solomon encoded > test vectors provided in the 802.16 standard. The systematic part is fine, > the problem is with the parity bits.
I did a quick search but couldn't find the standard. What is specified in the standard? In order to get the same vectors, you should: 1. Use the same Galois Field as is used in the standard 2. Use the same generator polynomial as in the standard Otherwise the parity bits will differ.
> I'm using Matlab to simulate the RS > encoding (using rsenc). Anybody has had a similar problem? Any Matlab > source code available to generate the "right" codewords? Thanks for your > help!
I have some RS routines that I wrote myself in Matlab (RS systematic encoding and the Massey-Berlekamp errors-and-erasures decoding algorithm. I haven't tried to change the Galois Field (using a different primitive polynomial to define the field) but I think it would be easy, though the speed of the algorithms might be affected. Hope this helps a bit Jaco Versfeld (Please reply to the newsgroup, the hotmail address has expired)
Hi

I'm having exactly the same problem. The first test vector refers to full
bandwidth (16 subchannels) using QPSK and overall coding rate 3/4. The RS
code you use is (40,36,2). According to the test vectors, if the input to
the RS coder is "D4 BA A1 12 F2 74 96 30 27 D4 88 9C 96 E3 A9 52 B3 15 AB
FD 92 53 07 32 C0 62 48 F0 19 22 E0 91 62 1A C1 00" (where the last 00 is
added manually as specified), the spec says the first 4 bytes of the
parity should "49 31 40 BF". However, I get "07 46 16 FC A9 06 42 28 2F C3
C2 49 90 22 95 82" (these are all 16 bytes, not just the first 4). I am
definately using the correct RS parameters, am zero pre-padding correctly
and believe I'm using the correct byte ordering (although I've tried just
about all permutation of bit and byte ordering I can think of). I have
tried two completely independent implemtations of the RS coder (one is
"rsenc" in Matlab, the other is a free C one I found on the net). I also
verified the operation of the latter one against a worked example in Sklar
(2nd ed). Did you manage to fix you problem? Has anyone else had this
problem.

Thanks for any help!
VB

>Hi-- > >I'm having difficulty getting the same results as the Reed-Solomon
encoded
>test vectors provided in the 802.16 standard. The systematic part is
fine,
>the problem is with the parity bits. I'm using Matlab to simulate the
RS
>encoding (using rsenc). Anybody has had a similar problem? Any Matlab >source code available to generate the "right" codewords? Thanks for
your
>help! > > > > >This message was sent using the Comp.DSP web interface on >www.DSPRelated.com >
This message was sent using the Comp.DSP web interface on www.DSPRelated.com
Things to note that might cause the messup if not taken care of:
1 MSB-first bit/byte conversion, which produces the polynomial
representation of elements in GF(256);
2 The input message to the RS encoder should look like ['inserted
all-zero-byte prefix' 'actual message symbols' '0x00 tail byte'] with the
leftmost symbol being the most significant in the corresponding message
polynomial.
3 Those most significant coeffients in the remainder polynomial (used for
generating parity symbols in systematic coding. Check Wicker's 'error
control systems' for detail.) are taken. (Seems you haven't got this far
yet.)

>Hi > >I'm having exactly the same problem. The first test vector refers to
full
>bandwidth (16 subchannels) using QPSK and overall coding rate 3/4. The
RS
>code you use is (40,36,2). According to the test vectors, if the input
to
>the RS coder is "D4 BA A1 12 F2 74 96 30 27 D4 88 9C 96 E3 A9 52 B3 15
AB
>FD 92 53 07 32 C0 62 48 F0 19 22 E0 91 62 1A C1 00" (where the last 00
is
>added manually as specified), the spec says the first 4 bytes of the >parity should "49 31 40 BF". However, I get "07 46 16 FC A9 06 42 28 2F
C3
>C2 49 90 22 95 82" (these are all 16 bytes, not just the first 4). I am >definately using the correct RS parameters, am zero pre-padding
correctly
>and believe I'm using the correct byte ordering (although I've tried
just
>about all permutation of bit and byte ordering I can think of). I have >tried two completely independent implemtations of the RS coder (one is >"rsenc" in Matlab, the other is a free C one I found on the net). I also >verified the operation of the latter one against a worked example in
Sklar
>(2nd ed). Did you manage to fix you problem? Has anyone else had this >problem. > >Thanks for any help! >VB > >>Hi-- >> >>I'm having difficulty getting the same results as the Reed-Solomon >encoded >>test vectors provided in the 802.16 standard. The systematic part is >fine, >>the problem is with the parity bits. I'm using Matlab to simulate the >RS >>encoding (using rsenc). Anybody has had a similar problem? Any Matlab >>source code available to generate the "right" codewords? Thanks for >your >>help! >> >> >> >> >>This message was sent using the Comp.DSP web interface on >>www.DSPRelated.com >> > > > > > >This message was sent using the Comp.DSP web interface on >www.DSPRelated.com >
This message was sent using the Comp.DSP web interface on www.DSPRelated.com
Hello,
i have already the same problem. Maybe you can send some Matlab Code which
solve the problem.

I tried the following:

y =
['D4';'BA';'A1';'12';'F2';'74';'96';'30';'27';'D4';'88';'9C';'96';'E3';'A9';'52';'B3';'15';'AB';'FD';'92';'53';'07';'32';'C0';'62';'48';'F0';'19';'22';'E0';'91';'62';'1A';'C1'];

y = hex2dec(y)';
y = [y';0];
msg = gf(y,8)';
code = rsenc(msg,52,36,rsgenpoly(255,239))

and so i get for the redundancy bits in decimal:
7     70     22    252    169      6     66     40     47    195    194   
 73    144     34    149    130

maybe you have another solution

thanks dirk

>Things to note that might cause the messup if not taken care of: >1 MSB-first bit/byte conversion, which produces the polynomial >representation of elements in GF(256); >2 The input message to the RS encoder should look like ['inserted >all-zero-byte prefix' 'actual message symbols' '0x00 tail byte'] with
the
>leftmost symbol being the most significant in the corresponding message >polynomial. >3 Those most significant coeffients in the remainder polynomial (used
for
>generating parity symbols in systematic coding. Check Wicker's 'error >control systems' for detail.) are taken. (Seems you haven't got this far >yet.) > >>Hi >> >>I'm having exactly the same problem. The first test vector refers to >full >>bandwidth (16 subchannels) using QPSK and overall coding rate 3/4. The >RS >>code you use is (40,36,2). According to the test vectors, if the input >to >>the RS coder is "D4 BA A1 12 F2 74 96 30 27 D4 88 9C 96 E3 A9 52 B3 15 >AB >>FD 92 53 07 32 C0 62 48 F0 19 22 E0 91 62 1A C1 00" (where the last 00 >is >>added manually as specified), the spec says the first 4 bytes of the >>parity should "49 31 40 BF". However, I get "07 46 16 FC A9 06 42 28 2F >C3 >>C2 49 90 22 95 82" (these are all 16 bytes, not just the first 4). I am >>definately using the correct RS parameters, am zero pre-padding >correctly >>and believe I'm using the correct byte ordering (although I've tried >just >>about all permutation of bit and byte ordering I can think of). I have >>tried two completely independent implemtations of the RS coder (one is >>"rsenc" in Matlab, the other is a free C one I found on the net). I
also
>>verified the operation of the latter one against a worked example in >Sklar >>(2nd ed). Did you manage to fix you problem? Has anyone else had this >>problem. >> >>Thanks for any help! >>VB >> >>>Hi-- >>> >>>I'm having difficulty getting the same results as the Reed-Solomon >>encoded >>>test vectors provided in the 802.16 standard. The systematic part is >>fine, >>>the problem is with the parity bits. I'm using Matlab to simulate the >>RS >>>encoding (using rsenc). Anybody has had a similar problem? Any
Matlab
>>>source code available to generate the "right" codewords? Thanks for >>your >>>help! >>> >>> >>> >>> >>>This message was sent using the Comp.DSP web interface on >>>www.DSPRelated.com >>> >> >> >> >> >> >>This message was sent using the Comp.DSP web interface on >>www.DSPRelated.com >> > > > > > >This message was sent using the Comp.DSP web interface on >www.DSPRelated.com >
I've found the "canned" Reed-Solomon function does not generate the same 
check bytes as the example.  Also, as previously stated, you really have 
to be careful about bit ordering, and pad your 36-byte message up to 239 
bytes (leading zeros).  Assuming you've got the bits in the right order, 
try creating your own generator polynomial as shown here.  Note that the 
primitive polynomial x^8 + x^4 + x^3 + x^2 + 1 is 285 decimal:

polyVal     = rsgenpoly(255,239,285,0);
encodedData = rsenc(gf(msg,8), 255, 239, gf(polyVal,8));

Now, decoding with built-in Matlab functions?  Good luck...

Hope this helps,
Ron Murias


In article <VOydnWHJqLkEj_veRVn-jw@giganews.com>,
 "dicze" <dirkczepluch@gmx.net> wrote:

> Hello, > i have already the same problem. Maybe you can send some Matlab Code which > solve the problem. > > I tried the following: > > y = > ['D4';'BA';'A1';'12';'F2';'74';'96';'30';'27';'D4';'88';'9C';'96';'E3';'A9';'5 > 2';'B3';'15';'AB';'FD';'92';'53';'07';'32';'C0';'62';'48';'F0';'19';'22';'E0'; > '91';'62';'1A';'C1']; > > y = hex2dec(y)'; > y = [y';0]; > msg = gf(y,8)'; > code = rsenc(msg,52,36,rsgenpoly(255,239)) > > and so i get for the redundancy bits in decimal: > 7 70 22 252 169 6 66 40 47 195 194 > 73 144 34 149 130 > > maybe you have another solution > > thanks dirk > > >Things to note that might cause the messup if not taken care of: > >1 MSB-first bit/byte conversion, which produces the polynomial > >representation of elements in GF(256); > >2 The input message to the RS encoder should look like ['inserted > >all-zero-byte prefix' 'actual message symbols' '0x00 tail byte'] with > the > >leftmost symbol being the most significant in the corresponding message > >polynomial. > >3 Those most significant coeffients in the remainder polynomial (used > for > >generating parity symbols in systematic coding. Check Wicker's 'error > >control systems' for detail.) are taken. (Seems you haven't got this far > >yet.) > > > >>Hi > >> > >>I'm having exactly the same problem. The first test vector refers to > >full > >>bandwidth (16 subchannels) using QPSK and overall coding rate 3/4. The > >RS > >>code you use is (40,36,2). According to the test vectors, if the input > >to > >>the RS coder is "D4 BA A1 12 F2 74 96 30 27 D4 88 9C 96 E3 A9 52 B3 15 > >AB > >>FD 92 53 07 32 C0 62 48 F0 19 22 E0 91 62 1A C1 00" (where the last 00 > >is > >>added manually as specified), the spec says the first 4 bytes of the > >>parity should "49 31 40 BF". However, I get "07 46 16 FC A9 06 42 28 2F > >C3 > >>C2 49 90 22 95 82" (these are all 16 bytes, not just the first 4). I am > >>definately using the correct RS parameters, am zero pre-padding > >correctly > >>and believe I'm using the correct byte ordering (although I've tried > >just > >>about all permutation of bit and byte ordering I can think of). I have > >>tried two completely independent implemtations of the RS coder (one is > >>"rsenc" in Matlab, the other is a free C one I found on the net). I > also > >>verified the operation of the latter one against a worked example in > >Sklar > >>(2nd ed). Did you manage to fix you problem? Has anyone else had this > >>problem. > >> > >>Thanks for any help! > >>VB > >> > >>>Hi-- > >>> > >>>I'm having difficulty getting the same results as the Reed-Solomon > >>encoded > >>>test vectors provided in the 802.16 standard. The systematic part is > >>fine, > >>>the problem is with the parity bits. I'm using Matlab to simulate the > >>RS > >>>encoding (using rsenc). Anybody has had a similar problem? Any > Matlab > >>>source code available to generate the "right" codewords? Thanks for > >>your > >>>help! > >>> > >>> > >>> > >>> > >>>This message was sent using the Comp.DSP web interface on > >>>www.DSPRelated.com > >>> > >> > >> > >> > >> > >> > >>This message was sent using the Comp.DSP web interface on > >>www.DSPRelated.com > >> > > > > > > > > > > > >This message was sent using the Comp.DSP web interface on > >www.DSPRelated.com > >
Hi!

I am interested in the answer to the question discussed a while ago on
compatibility of RS Encoder/Decoder in MATLAB with the example shown in
802.16 standard. I read the discussion but I could not find a solution for
it. It would be appreciated if you could guide me to the answer.

Thanks in advance,
Moonlight_vodka





>I've found the "canned" Reed-Solomon function does not generate the same
>check bytes as the example. Also, as previously stated, you really have
>to be careful about bit ordering, and pad your 36-byte message up to 239
>bytes (leading zeros). Assuming you've got the bits in the right order,
>try creating your own generator polynomial as shown here. Note that the
>primitive polynomial x^8 + x^4 + x^3 + x^2 + 1 is 285 decimal: > >polyVal = rsgenpoly(255,239,285,0); >encodedData = rsenc(gf(msg,8), 255, 239, gf(polyVal,8)); > >Now, decoding with built-in Matlab functions? Good luck... > >Hope this helps, >Ron Murias > > >In article <VOydnWHJqLkEj_veRVn-jw@giganews.com>, > "dicze" <dirkczepluch@gmx.net> wrote: > >> Hello, >> i have already the same problem. Maybe you can send some Matlab Code
which
>> solve the problem. >> >> I tried the following: >> >> y = >>
['D4';'BA';'A1';'12';'F2';'74';'96';'30';'27';'D4';'88';'9C';'96';'E3';'A9';'5
>>
2';'B3';'15';'AB';'FD';'92';'53';'07';'32';'C0';'62';'48';'F0';'19';'22';'E0';
>> '91';'62';'1A';'C1']; >> >> y = hex2dec(y)'; >> y = [y';0]; >> msg = gf(y,8)'; >> code = rsenc(msg,52,36,rsgenpoly(255,239)) >> >> and so i get for the redundancy bits in decimal: >> 7 70 22 252 169 6 66 40 47 195 194
>> 73 144 34 149 130 >> >> maybe you have another solution >> >> thanks dirk >> >> >Things to note that might cause the messup if not taken care of: >> >1 MSB-first bit/byte conversion, which produces the polynomial >> >representation of elements in GF(256); >> >2 The input message to the RS encoder should look like ['inserted >> >all-zero-byte prefix' 'actual message symbols' '0x00 tail byte'] with >> the >> >leftmost symbol being the most significant in the corresponding
message
>> >polynomial. >> >3 Those most significant coeffients in the remainder polynomial (used >> for >> >generating parity symbols in systematic coding. Check Wicker's 'error >> >control systems' for detail.) are taken. (Seems you haven't got this
far
>> >yet.) >> > >> >>Hi >> >> >> >>I'm having exactly the same problem. The first test vector refers to >> >full >> >>bandwidth (16 subchannels) using QPSK and overall coding rate 3/4.
The
>> >RS >> >>code you use is (40,36,2). According to the test vectors, if the
input
>> >to >> >>the RS coder is "D4 BA A1 12 F2 74 96 30 27 D4 88 9C 96 E3 A9 52 B3
15
>> >AB >> >>FD 92 53 07 32 C0 62 48 F0 19 22 E0 91 62 1A C1 00" (where the last
00
>> >is >> >>added manually as specified), the spec says the first 4 bytes of the >> >>parity should "49 31 40 BF". However, I get "07 46 16 FC A9 06 42 28
2F
>> >C3 >> >>C2 49 90 22 95 82" (these are all 16 bytes, not just the first 4). I
am
>> >>definately using the correct RS parameters, am zero pre-padding >> >correctly >> >>and believe I'm using the correct byte ordering (although I've tried >> >just >> >>about all permutation of bit and byte ordering I can think of). I
have
>> >>tried two completely independent implemtations of the RS coder (one
is
>> >>"rsenc" in Matlab, the other is a free C one I found on the net). I >> also >> >>verified the operation of the latter one against a worked example in >> >Sklar >> >>(2nd ed). Did you manage to fix you problem? Has anyone else had
this
>> >>problem. >> >> >> >>Thanks for any help! >> >>VB >> >> >> >>>Hi-- >> >>> >> >>>I'm having difficulty getting the same results as the Reed-Solomon >> >>encoded >> >>>test vectors provided in the 802.16 standard. The systematic part
is
>> >>fine, >> >>>the problem is with the parity bits. I'm using Matlab to simulate
the
>> >>RS >> >>>encoding (using rsenc). Anybody has had a similar problem? Any >> Matlab >> >>>source code available to generate the "right" codewords? Thanks
for
>> >>your >> >>>help! >> >>> >> >>> >> >>> >> >>> >> >>>This message was sent using the Comp.DSP web interface on >> >>>www.DSPRelated.com >> >>> >> >> >> >> >> >> >> >> >> >> >> >>This message was sent using the Comp.DSP web interface on >> >>www.DSPRelated.com >> >> >> > >> > >> > >> > >> > >> >This message was sent using the Comp.DSP web interface on >> >www.DSPRelated.com >> > >
moonlight_vodka wrote:
> Hi! > > I am interested in the answer to the question discussed a while ago on > compatibility of RS Encoder/Decoder in MATLAB with the example shown in > 802.16 standard. I read the discussion but I could not find a solution for > it. It would be appreciated if you could guide me to the answer. > > Thanks in advance, > Moonlight_vodka >
Did you try b=1 as well as b=0?
> > > >> I've found the "canned" Reed-Solomon function does not generate the same > >> check bytes as the example. Also, as previously stated, you really have > >> to be careful about bit ordering, and pad your 36-byte message up to 239 > >> bytes (leading zeros). Assuming you've got the bits in the right order, > >> try creating your own generator polynomial as shown here. Note that the > >> primitive polynomial x^8 + x^4 + x^3 + x^2 + 1 is 285 decimal: >> >> polyVal = rsgenpoly(255,239,285,0); >> encodedData = rsenc(gf(msg,8), 255, 239, gf(polyVal,8)); >> >> Now, decoding with built-in Matlab functions? Good luck... >> >> Hope this helps, >> Ron Murias >> >> >> In article <VOydnWHJqLkEj_veRVn-jw@giganews.com>, >> "dicze" <dirkczepluch@gmx.net> wrote: >> >>> Hello, >>> i have already the same problem. Maybe you can send some Matlab Code > which >>> solve the problem. >>> >>> I tried the following: >>> >>> y = >>> > ['D4';'BA';'A1';'12';'F2';'74';'96';'30';'27';'D4';'88';'9C';'96';'E3';'A9';'5 > 2';'B3';'15';'AB';'FD';'92';'53';'07';'32';'C0';'62';'48';'F0';'19';'22';'E0'; >>> '91';'62';'1A';'C1']; >>> >>> y = hex2dec(y)'; >>> y = [y';0]; >>> msg = gf(y,8)'; >>> code = rsenc(msg,52,36,rsgenpoly(255,239)) >>> >>> and so i get for the redundancy bits in decimal: >>> 7 70 22 252 169 6 66 40 47 195 194 > >>> 73 144 34 149 130 >>> >>> maybe you have another solution >>> >>> thanks dirk >>> >>>> Things to note that might cause the messup if not taken care of: >>>> 1 MSB-first bit/byte conversion, which produces the polynomial >>>> representation of elements in GF(256); >>>> 2 The input message to the RS encoder should look like ['inserted >>>> all-zero-byte prefix' 'actual message symbols' '0x00 tail byte'] with >>> the >>>> leftmost symbol being the most significant in the corresponding > message >>>> polynomial. >>>> 3 Those most significant coeffients in the remainder polynomial (used >>> for >>>> generating parity symbols in systematic coding. Check Wicker's 'error >>>> control systems' for detail.) are taken. (Seems you haven't got this > far >>>> yet.) >>>> >>>>> Hi >>>>> >>>>> I'm having exactly the same problem. The first test vector refers to >>>> full >>>>> bandwidth (16 subchannels) using QPSK and overall coding rate 3/4. > The >>>> RS >>>>> code you use is (40,36,2). According to the test vectors, if the > input >>>> to >>>>> the RS coder is "D4 BA A1 12 F2 74 96 30 27 D4 88 9C 96 E3 A9 52 B3 > 15 >>>> AB >>>>> FD 92 53 07 32 C0 62 48 F0 19 22 E0 91 62 1A C1 00" (where the last > 00 >>>> is >>>>> added manually as specified), the spec says the first 4 bytes of the >>>>> parity should "49 31 40 BF". However, I get "07 46 16 FC A9 06 42 28 > 2F >>>> C3 >>>>> C2 49 90 22 95 82" (these are all 16 bytes, not just the first 4). I > am >>>>> definately using the correct RS parameters, am zero pre-padding >>>> correctly >>>>> and believe I'm using the correct byte ordering (although I've tried >>>> just >>>>> about all permutation of bit and byte ordering I can think of). I > have >>>>> tried two completely independent implemtations of the RS coder (one > is >>>>> "rsenc" in Matlab, the other is a free C one I found on the net). I >>> also >>>>> verified the operation of the latter one against a worked example in >>>> Sklar >>>>> (2nd ed). Did you manage to fix you problem? Has anyone else had > this >>>>> problem. >>>>> >>>>> Thanks for any help! >>>>> VB >>>>> >>>>>> Hi-- >>>>>> >>>>>> I'm having difficulty getting the same results as the Reed-Solomon >>>>> encoded >>>>>> test vectors provided in the 802.16 standard. The systematic part > is >>>>> fine, >>>>>> the problem is with the parity bits. I'm using Matlab to simulate > the >>>>> RS >>>>>> encoding (using rsenc). Anybody has had a similar problem? Any >>> Matlab >>>>>> source code available to generate the "right" codewords? Thanks > for >>>>> your >>>>>> help! >>>>>>
Hello,

This is worked Matlab code:

y =
['D4';'BA';'A1';'12';'F2';'74';'96';'30';'27';'D4';'88';'9C';'96';'E3';'A9';'52';'B3';'15';'AB';'FD';'92';'53';'07';'32';'C0';'62';'48';'F0';'19';'22';'E0';'91';'62';'1A';'C1'];
y = hex2dec(y);
yk=[zeros(1,203) y' 0]; % Make source data
m = 8; % Number of bits per symbol
n = 2^m-1; % Word lengths for code
k= 239; % Number of information symbols
msg=gf([yk],m); % Galois array
gen=rsgenpoly(n,k,285,0) % Specify RS generation polynomial
code = rsenc(msg,n,k,gen) % Encode the information symbols

Enjoy!

Andrey.


>Hello, > >This is worked Matlab code: > >y = >['D4';'BA';'A1';'12';'F2';'74';'96';'30';'27';'D4';'88';'9C';'96';'E3';'A9';'52';'B3';'15';'AB';'FD';'92';'53';'07';'32';'C0';'62';'48';'F0';'19';'22';'E0';'91';'62';'1A';'C1']; >y = hex2dec(y); >yk=[zeros(1,203) y' 0]; % Make source data >m = 8; % Number of bits per symbol >n = 2^m-1; % Word lengths for code >k= 239; % Number of information symbols >msg=gf([yk],m); % Galois array >gen=rsgenpoly(n,k,285,0) % Specify RS generation polynomial >code = rsenc(msg,n,k,gen) % Encode the information symbols > >Enjoy! > >Andrey. > > >
Just to be completely clear, the reason this version works and the earlier versions don't is because of the final 0 in gen=rsgenpoly(n,k,285,0). The 802.16 standard says the generator polynomial should be g(x) = (x + lambda**0) * (x + lambda**1) * ... (x + lambda**(2*T-1)), however when using Matlab to create the generator polynomial, unless you explicitly set the 4th parameter "b" to 0, you will get g(x) = (x + lambda**1) * ...