Forums

Need help decoding shortened Reed-Solomon (24,12,13) using c++

Started by matt d November 19, 2013
Hello,

I am working on an academic project.  I need to do Reed-Solomon decoding on
data payload bits encoded with the shortened (24,12,13) RS code over
GF(2^6).  I prefer Simon Rockliff's rs.c code because of its relative
simplicity.  However, I am having two problems. (1) I need to make the code
handle the shortened code which is shortened by deleting the 39 left most
info symbols;  And (2) and I need to how to group the data bits (which are
currently in a 144-bit array) into 24 6-bit symbols so i can give the
codeword to the decoder. 

I have been unable to find help with this issue anywhere.  I will be super
appreciative for any guidance.  

Thanks!
Matt D
---------------

	 

_____________________________		
Posted through www.DSPRelated.com
On Tue, 19 Nov 2013 09:02:26 -0600, "matt d" <98932@dsprelated> wrote:

>Hello, > >I am working on an academic project. I need to do Reed-Solomon decoding on >data payload bits encoded with the shortened (24,12,13) RS code over >GF(2^6). I prefer Simon Rockliff's rs.c code because of its relative >simplicity. However, I am having two problems. (1) I need to make the code >handle the shortened code which is shortened by deleting the 39 left most >info symbols; And (2) and I need to how to group the data bits (which are >currently in a 144-bit array) into 24 6-bit symbols so i can give the >codeword to the decoder.
The usual procedure when shortening a block code is to generate the codeword in the encoder with zeros in the symbols that will be deleted. In the decoder, then, the entire codeword is decoded with the received symbols and zeros in place of the deleted symbols. It's pretty simple, but it does depend on the encoder and decoder doing the same thing to the same symbols. The memory issue depends on the software implementation, which I'm unfamiliar with so I can't help there.
>I have been unable to find help with this issue anywhere. I will be super >appreciative for any guidance. > >Thanks! >Matt D >--------------- > > > >_____________________________ >Posted through www.DSPRelated.com
Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
>The usual procedure when shortening a block code is to generate the >codeword in the encoder with zeros in the symbols that will be >deleted. In the decoder, then, the entire codeword is decoded with >the received symbols and zeros in place of the deleted symbols.
In this case I am not sure the data is encoded with the whole 63 symbols. In my problem, the data payload of interest consists of 72 bits, and this is serialized into 12 hex-bits, or 6-bit symbols. These hex-bits are then encoded with the (24,12,13) RS code to yield 24 hex bits. the generator polynomial for the (24,12,13) shortened Reed-Solomon code is: g(x) = 50 + 41x + 02x^2 + 74x^3 + 11x^4 + 60x^5 + 34x^6 + 71x^7 + 03x^8 + 55x^9 + 05x^10 + 71x^11 + x^12 the coefficients are in octal while the exponents are in decimal. The (KxN or 12x24) generator matrix is constructed from the polynomial. in this case the natural expression for the generator matrix uses hex bit symbols.
>It's pretty simple, but it does depend on the encoder and decoder >doing the same thing to the same symbols. > >The memory issue depends on the software implementation, which I'm >unfamiliar with so I can't help there.
I am trying to solve this problem in terminal using gcc (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2 and the standard c++. the decoder will take a 24 symbol codeword, but i am unclear how to put the bits into 6-bit symbols? maybe use a 24x6 multidimensional array? do some kind of conversion like from binary to octal? This has had me stumped for a long time, and i have not found anywhere on the net to turn to for help. Thanks soo much!!! _____________________________ Posted through www.DSPRelated.com
On Tue, 19 Nov 2013 11:41:06 -0600, "matt d" <98932@dsprelated> wrote:

> >>The usual procedure when shortening a block code is to generate the >>codeword in the encoder with zeros in the symbols that will be >>deleted. In the decoder, then, the entire codeword is decoded with >>the received symbols and zeros in place of the deleted symbols. > >In this case I am not sure the data is encoded with the whole 63 symbols. >In my problem, the data payload of interest consists of 72 bits, and this >is serialized into 12 hex-bits, or 6-bit symbols. These hex-bits are then >encoded with the (24,12,13) RS code to yield 24 hex bits.
A "shortened" code implies that the data field has been shortened from the native code. e.g., the very common (204, 188) Reed-Solomon code with 8-bit symbols, used in DVB and many other places, is shortened from a native (255, 239) code. I'm not quite sure what the 13 is for in your (24, 12, 13) code, as it is unlikely to be be t if n-k is 12. I'm also having trouble reconciling your earlier statement about 39 symbols being deleted for the shortening. As a result I'm a little unsure about your notational convention, but if your shortened code is (24,12), the native code (or mother code or whatever you want to call it) may be (31, 19) or something like that. The difference is usually zero-stuffed in both the encoder and decoder. Since you are using a library I would first guess that the decoder is built to work on the native code rather than a specific shortened code, but I'm unfamiliar with the library. In other words, maybe the library decoder is expecting the zero-stuffed (31, 19) mother code?
>the generator polynomial for the (24,12,13) shortened Reed-Solomon code >is: > >g(x) = 50 + 41x + 02x^2 + 74x^3 + 11x^4 + 60x^5 + 34x^6 + 71x^7 + 03x^8 + >55x^9 + 05x^10 + 71x^11 + x^12 >the coefficients are in octal while the exponents are in decimal. The (KxN >or 12x24) generator matrix is constructed from the polynomial. in this >case the natural expression for the generator matrix uses hex bit symbols. > > > >>It's pretty simple, but it does depend on the encoder and decoder >>doing the same thing to the same symbols. >> >>The memory issue depends on the software implementation, which I'm >>unfamiliar with so I can't help there. > >I am trying to solve this problem in terminal using gcc (Ubuntu/Linaro >4.7.2-2ubuntu1) 4.7.2 >and the standard c++. the decoder will take a 24 symbol codeword, but i am >unclear how to put the bits into 6-bit symbols? maybe use a 24x6 >multidimensional array? do some kind of conversion like from binary to >octal? This has had me stumped for a long time, and i have not found >anywhere on the net to turn to for help.
Are you doing the encoder as well? As long as you do the same thing at both ends you should be fine.
> >Thanks soo much!!! > > > >_____________________________ >Posted through www.DSPRelated.com
Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
>On Tue, 19 Nov 2013 11:41:06 -0600, "matt d" <98932@dsprelated> wrote:
> >A "shortened" code implies that the data field has been shortened from >the native code. e.g., the very common (204, 188) Reed-Solomon code >with 8-bit symbols, used in DVB and many other places, is shortened >from a native (255, 239) code. I'm not quite sure what the 13 is for >in your (24, 12, 13) code, as it is unlikely to be be t if n-k is 12. >I'm also having trouble reconciling your earlier statement about 39 >symbols being deleted for the shortening. As a result I'm a little >unsure about your notational convention, but if your shortened code is >(24,12), the native code (or mother code or whatever you want to call >it) may be (31, 19) or something like that.
The notation I am using is (N,K,D) N=number of symbols, K=number of parity symbols, D=distance. the code is shortened from the length of 63. So the native code was (63,51,13).
>The difference is usually zero-stuffed in both the encoder and >decoder. Since you are using a library I would first guess that the >decoder is built to work on the native code rather than a specific >shortened code, but I'm unfamiliar with the library. In other words, >maybe the library decoder is expecting the zero-stuffed (31, 19) >mother code? >
unfortunately i have no library for the decoding. and i am trying to use Simon Rockliff's rs.c to do the decoding. but i have seen the same encoding process in python code. it builds the 24 symbol codeword like this: def rs_24_12_13_encode(data): matrix = ( (1,0,0,0,0,0,0,0,0,0,0,0,062,044,003,025,014,016,027,003,053,004,036,047), (0,1,0,0,0,0,0,0,0,0,0,0,011,012,011,011,016,064,067,055,001,076,026,073), (0,0,1,0,0,0,0,0,0,0,0,0,003,001,005,075,014,006,020,044,066,006,070,066), (0,0,0,1,0,0,0,0,0,0,0,0,021,070,027,045,016,067,023,064,073,033,044,021), (0,0,0,0,1,0,0,0,0,0,0,0,030,022,003,075,015,015,033,015,051,003,053,050), (0,0,0,0,0,1,0,0,0,0,0,0,001,041,027,056,076,064,021,053,004,025,001,012), (0,0,0,0,0,0,1,0,0,0,0,0,061,076,021,055,076,001,063,035,030,013,064,070), (0,0,0,0,0,0,0,1,0,0,0,0,024,022,071,056,021,035,073,042,057,074,043,076), (0,0,0,0,0,0,0,0,1,0,0,0,072,042,005,020,043,047,033,056,001,016,013,076), (0,0,0,0,0,0,0,0,0,1,0,0,072,014,065,054,035,025,041,016,015,040,071,026), (0,0,0,0,0,0,0,0,0,0,1,0,073,065,036,061,042,022,017,004,044,020,025,005), (0,0,0,0,0,0,0,0,0,0,0,1,071,005,055,003,071,034,060,011,074,002,041,050)) assert data < 2**72 codeword = [0,] * 24 for i in range(24): for j in range(12): hexbit = (data >> ((11 - j) * 6)) & 0x3f codeword[i] ^= gf6mult(hexbit, matrix[j][i]) return codeword ------end code-------- looks to me like a 12 6-bit integers (maybe in an array with 12 posititions??) are multiplied by this 12x24 matrix to produce the 24 6-bit symbols to create the 24 hex-bit codeword. i don't see anything about padding with zeros.
>>the generator polynomial for the (24,12,13) shortened Reed-Solomon code >>is: >> >>g(x) = 50 + 41x + 02x^2 + 74x^3 + 11x^4 + 60x^5 + 34x^6 + 71x^7 + 03x^8
+
>>55x^9 + 05x^10 + 71x^11 + x^12 >>the coefficients are in octal while the exponents are in decimal. The
(KxN
>>or 12x24) generator matrix is constructed from the polynomial. in this >>case the natural expression for the generator matrix uses hex bit
symbols.
>>
Any ideas will be much appreciated! Thanks for the discussion! Regards Matt D ------------------------------------ _____________________________ Posted through www.DSPRelated.com
On Tue, 19 Nov 2013 16:13:43 -0600, "matt d" <98932@dsprelated> wrote:

>>On Tue, 19 Nov 2013 11:41:06 -0600, "matt d" <98932@dsprelated> wrote: > >> >>A "shortened" code implies that the data field has been shortened from >>the native code. e.g., the very common (204, 188) Reed-Solomon code >>with 8-bit symbols, used in DVB and many other places, is shortened >>from a native (255, 239) code. I'm not quite sure what the 13 is for >>in your (24, 12, 13) code, as it is unlikely to be be t if n-k is 12. >>I'm also having trouble reconciling your earlier statement about 39 >>symbols being deleted for the shortening. As a result I'm a little >>unsure about your notational convention, but if your shortened code is >>(24,12), the native code (or mother code or whatever you want to call >>it) may be (31, 19) or something like that. > >The notation I am using is (N,K,D) N=number of symbols, K=number of parity >symbols, D=distance. the code is shortened from the length of 63. So the >native code was (63,51,13). > >>The difference is usually zero-stuffed in both the encoder and >>decoder. Since you are using a library I would first guess that the >>decoder is built to work on the native code rather than a specific >>shortened code, but I'm unfamiliar with the library. In other words, >>maybe the library decoder is expecting the zero-stuffed (31, 19) >>mother code? >> >unfortunately i have no library for the decoding. and i am trying to use >Simon Rockliff's rs.c to do the decoding.
That's the library I was referring to. In other words, you're using somebody else's implementation, which I'd first assume was generic, i.e., doesn't assume shortening. My assumption there could be wrong, though, and the implementation may be smart enough to sort out shortening if configured correctly. In that case, you're at the mercy of the assumptions made in the implementation, but you may be able to sort out what those were if the code documentation doesn't make it explicit.
> but i have seen the same >encoding process in python code.
Same as what? Are you sure they're the same?
> it builds the 24 symbol codeword like >this: > >def rs_24_12_13_encode(data): > matrix = ( >(1,0,0,0,0,0,0,0,0,0,0,0,062,044,003,025,014,016,027,003,053,004,036,047), >(0,1,0,0,0,0,0,0,0,0,0,0,011,012,011,011,016,064,067,055,001,076,026,073), >(0,0,1,0,0,0,0,0,0,0,0,0,003,001,005,075,014,006,020,044,066,006,070,066), >(0,0,0,1,0,0,0,0,0,0,0,0,021,070,027,045,016,067,023,064,073,033,044,021), >(0,0,0,0,1,0,0,0,0,0,0,0,030,022,003,075,015,015,033,015,051,003,053,050), > (0,0,0,0,0,1,0,0,0,0,0,0,001,041,027,056,076,064,021,053,004,025,001,012), > (0,0,0,0,0,0,1,0,0,0,0,0,061,076,021,055,076,001,063,035,030,013,064,070), > (0,0,0,0,0,0,0,1,0,0,0,0,024,022,071,056,021,035,073,042,057,074,043,076), > (0,0,0,0,0,0,0,0,1,0,0,0,072,042,005,020,043,047,033,056,001,016,013,076), > (0,0,0,0,0,0,0,0,0,1,0,0,072,014,065,054,035,025,041,016,015,040,071,026), > (0,0,0,0,0,0,0,0,0,0,1,0,073,065,036,061,042,022,017,004,044,020,025,005), > (0,0,0,0,0,0,0,0,0,0,0,1,071,005,055,003,071,034,060,011,074,002,041,050)) > assert data < 2**72 > codeword = [0,] * 24 > for i in range(24): > for j in range(12): > hexbit = (data >> ((11 - j) * 6)) & 0x3f > codeword[i] ^= gf6mult(hexbit, matrix[j][i]) > return codeword >------end code-------- > >looks to me like a 12 6-bit integers (maybe in an array with 12 >posititions??) are multiplied by this 12x24 matrix to produce the 24 6-bit >symbols to create the 24 hex-bit codeword. i don't see anything about >padding with zeros.
Note that the left 12 columns make up an identity matrix (for the data field). If the data field identity matrix were extended upward 39 more rows (that's the 39 6-bit symbols that got deleted) so that the identity matrix was 51x51 instead of 12x12, you'd have the whole encoder (assuming you had the parity field to go with it). Since the encoder appears to be implemented with just the rightmost 12 rows, you don't see the others, which implies that they're zeros. This means that either a) you can configure the decoder for the full (63, 51) code, replace the 39 6-bit zeroes for each received codeword, and decode it as the native code, or b) confirm that the decoder you have really does know how to either do a) automatically or decode the shortened code properly. You can probably test it with a) and then see if you can get to b). Unless somebody here is familiar with the implementation you're using you'll have to sort that out yourself or ask the author or somebody else familiar with it. Perhaps there's documentation with the code that helps with that.
>>>the generator polynomial for the (24,12,13) shortened Reed-Solomon code >>>is: >>> >>>g(x) = 50 + 41x + 02x^2 + 74x^3 + 11x^4 + 60x^5 + 34x^6 + 71x^7 + 03x^8 >+ >>>55x^9 + 05x^10 + 71x^11 + x^12 >>>the coefficients are in octal while the exponents are in decimal. The >(KxN >>>or 12x24) generator matrix is constructed from the polynomial. in this >>>case the natural expression for the generator matrix uses hex bit >symbols. >>> >Any ideas will be much appreciated! Thanks for the discussion! > >Regards >Matt D >------------------------------------ > > >_____________________________ >Posted through www.DSPRelated.com
Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
On Tue, 19 Nov 2013 22:59:14 GMT, eric.jacobsen@ieee.org (Eric
Jacobsen) wrote:

> Since the >encoder appears to be implemented with just the rightmost 12 rows, you >don't see the others, which implies that they're zeros.
Durrr...that should be the rightmost 12 columns of the identity matrix, not rightmost 12 rows. Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
>On Tue, 19 Nov 2013 22:59:14 GMT, eric.jacobsen@ieee.org (Eric >Jacobsen) wrote: > >> Since the >>encoder appears to be implemented with just the rightmost 12 rows, you >>don't see the others, which implies that they're zeros. > >Durrr...that should be the rightmost 12 columns of the identity >matrix, not rightmost 12 rows. > > >Eric Jacobsen >Anchor Hill Communications >http://www.anchorhill.com >
so i figured a work around to make Simon Rockliffs rs.c handle a shortened code. simply set the parameters (N,K,) to the full code , in this case N = 2^6-1 = 63 and K = 51. the program will print the correct 24 symbols and an extra 39 zeros (0). but the extra zeros can just be discarded. i am very happy that i am able to use rs.c because of its simplicity of implementation. so many other programs are crazy hard to read and have like ten different files so they are a real pain to pop into a real application. Thanks everyone! _____________________________ Posted through www.DSPRelated.com
On Thu, 21 Nov 2013 22:22:51 -0600, "matt d" <98932@dsprelated> wrote:

>>On Tue, 19 Nov 2013 22:59:14 GMT, eric.jacobsen@ieee.org (Eric >>Jacobsen) wrote: >> >>> Since the >>>encoder appears to be implemented with just the rightmost 12 rows, you >>>don't see the others, which implies that they're zeros. >> >>Durrr...that should be the rightmost 12 columns of the identity >>matrix, not rightmost 12 rows. >> >> >>Eric Jacobsen >>Anchor Hill Communications >>http://www.anchorhill.com >> > >so i figured a work around to make Simon Rockliffs rs.c handle a shortened >code. simply set the parameters (N,K,) to the full code , in this case N >= 2^6-1 = 63 and K = 51. the program will print the correct 24 symbols >and an extra 39 zeros (0). but the extra zeros can just be discarded.
Exactly. That's what I was describing. You can use the decoder the same way, where you take the received codeword, fill in the 39 zeroes, and then decode the entire codeword. Many systems work this way, but there are also methods to optimize for the shortened codeword if that's all you'll ever use.
> i am very happy that i am able to use rs.c because of its simplicity of >implementation. so many other programs are crazy hard to read and have >like ten different files so they are a real pain to pop into a real >application. > >Thanks everyone! > >_____________________________ >Posted through www.DSPRelated.com
Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com