**Read the updates at the end! Comments are disabled because people don’t actually read the post. This is sad to me, since it really shows that the majority of people commenting on this post are really just trolling for a free pass at an implementation, think that I or someone else will send it to them or port it into C for them, and are so lazy that they can’t scroll through the post themselves.**

For part of my class project in coding theory this semester I’ve implemented the Guruswami-Sudan decoding algorithm for Reed-Solomon codes. Reed-Solomon codes are used widely in practice for error-control coding. For example, CDs use a Reed-Solomon code to provide resilience to errors introduced by scratches or machine error. The math behind RS codes is somewhat complicated, but the idea is as follows. Suppose you have some *k* symbols of data that you want to encode into *n* symbols. The redundancy (and hence error correction capability) can be thought of as the difference *(n – k)*. This is the “fat” we add into the data to make it resistant to errors.

RS codes take these *k* symbols and think of them as the coefficients of a polynomial

f(X) = f_0 + f_1 x + f_2 x^2 + … + f_{k-1} x^{k-1}

The encoder and decoder agree to fix *n* points *{a_1, a_2, … a_n}*. The encoding map consists of evaluating *f(X)* at these *n* points and sending the evaluations:

codeword = (f(a_1), f(a_2), … f(a_n))

The key is in decoding — if the decoder gets any *k* symbols correctly, it should be able to interpolate a unique polynomial *f* through them perfectly (this is from linear algebra). Thus in the CD example, if the CD player can’t read some of the symbols, it can only tell the decoder those symbols that it did read. As long as *k* of those symbols were received the decoder can recover the polynomial and hence the data sequence.

Now of course the math is a little more complicated than that, but not by too much. RS codes are actually defined as polynomials over the ring *F[x]* where *F* is the finite field with *2^m* elements, and the encoding is the evaluation of a degree *k-1* polynomial on all the nonzero elements of the field.

The Guruswami-Sudan algorithm algorithm works in two steps — it interpolates a certain bivariate polynomial *Q[x,y]* in a F[x,y], and then factors it into factors of the form *(y – f_i(x))*. The y-roots *{f_i(x)}* can be thought of as “candidate polynomials” for the data sequences. The algorithm works in polynomial time and outputs a small list of candidates which is guaranteed to contain the transmitted codeword under certain conditions on how bad the errors are. The real key is that the list will often contain the true codeword even if more errors occurred than the code was designed for.

My implementation is based on a very nice tutorial paper by Robert McEliece, who is a really fantastic writer. It uses the Koetter algorithm for interpolation and the Roth-Ruckenstein algorithm to factor the resulting polynomial. This posting is mostly so that Google will possibly pop up this page if people are looking for MATLAB implementations of this algorithm and don’t want to waste sleepless nights like I did trying to force it to work. Caveat emptor, as they always say.

UPDATE : More information here.

UPDATE 2 : Apparently people who comment on this post are incapable or too lazy to follow links. I **will not** email you my code — just follow the link above. I have neither the time nor the inclination to deal with requests on an individual basis. If you can’t get it on your own, perhaps you should find some other job that doesn’t require you to use computers.

May 24, 2005 at 5:30 am

I really appreciate for your help.

please send to me your RS matlab code.

Have a noce day~

May 26, 2005 at 8:07 am

I am working on implementation of RC encoder and decoder without the use of matlab function .I will really thankful to you if u send me the code .

June 3, 2005 at 7:26 pm

Hello Mr. Sarwate:

I am working on soft-decision decoding of RS codes. It would be great if you can send me your MATLAB code for the Guruswami-Sudan algorithm.

Than you for your assistance.

Romeo

June 3, 2005 at 7:36 pm

As an additional warning to people — the code is pretty ugly at the moment and too undocumented. I will be working on some better function descriptions etc sometime this month.

In addition, as with all MATLAB code, this is pretty slow, and I made little effort at optimization. Much of the Galois Field arithmetic in MATLAB is not vectorized in an obvious way, so I ended up using a lot of loop constructs, slowing things a lot.

June 7, 2005 at 1:31 pm

I’m working on Gs-decoding of Rs codes. If you can send the code of decoding algorithm it will be great. Thank you…

June 8, 2005 at 2:50 am

I am working on soft-decision decoding of RS codes. It would be great if you can send me your MATLAB code for the Guruswami-Sudan algorithm

June 24, 2005 at 2:20 am

hi,

can u send me the matlab codes for encoding and decoding rd codes.thanks in advence.

June 29, 2005 at 6:51 am

Plz send me ur matlab code for RS encoder/decoder

July 6, 2005 at 1:59 am

please send the matlab code for a image analysis

July 18, 2005 at 3:26 pm

If you send me the simulation codes, it will help me so much for my implementation works for soft decision RS decoding.

Thank you for your helps.

Good lucks…

July 19, 2005 at 3:46 am

iam working on rs coder,i want to implement in verilog.altera fpga

i will be very thankful to you if you send me the code for rs encoding and decoding in verilog.

thanking you.

August 1, 2005 at 11:28 pm

iam working on rs coder,i want to implement in verilog.altera fpga.It would be great if you can send me your MATLAB code

August 19, 2005 at 1:53 am

hello every body responsible on that site

I am happy to find such site in the internet

I am interesting in this field.. and lecturing the coding and cryptography

I hope to have ascientific communication with you.

Best Regards.

Dr. Eng. Sattar B. Sadkhan

Iraq

August 19, 2005 at 2:02 am

Is it possible to send me the MATLAB programs available in this field

Thanks in advance

August 20, 2005 at 6:58 am

Hello Mr. Sarwate:

I am working on soft-decision decoding of RS codes. It would be great if you can send me your MATLAB code for the Guruswami-Sudan algorithm.

I am waiting for your e-mail!

Thank you !

dingshan

August 23, 2005 at 1:42 am

please send me the matlab programs for reed solomon encoding and decoding (using berlekamp algorithm)

September 11, 2005 at 2:33 am

respected sir,

i am working on WiMAX OFDM PHY layer and i need ur matlab code on REED SOLOMON codes . I will be very greatful to u as they will be of valuable help to me.

thanking u in anticipation.

urs sincerely

vineet srivastava

vineet_bruce@rediffmail.com

September 29, 2005 at 1:29 am

hello everybody

i am workin on matlab simulation of wimax as my b.tech final year project… kindly help me by sending a detailed block diagram of 802.16

i will be waiting

September 30, 2005 at 6:57 pm

I am working on the LDPC based on RS Codes.

I really appreciate if you send me the RS matlab code.

Thank you

baexx026@umn.edu

October 17, 2005 at 11:30 pm

Hello Mr. Sarwate:

I am working on implementation of RS encoder and decoder without the use of matlab function .I will really thankful to you if u send me the code .

October 21, 2005 at 12:24 am

I’m working on implementation of LDPC decoder in xilinx FPGA.

I’ll be really thankful if you send me verilog code .

Thanks

A.Mohammed Mian

November 14, 2005 at 12:47 am

Can i please have the reed-solomon encoder/decoder matlab code? Thanks

November 17, 2005 at 3:11 am

sir,

i kindly reqest to send the matlab code for

reed-solomon encoder/decoder.thank you sir.

February 18, 2006 at 4:15 am

Sir,

I have an implementation of the Guruswami Sudan Decoder as well in C++ using NTL. The kotter interpolation algorithm works fine. But there is some big bug in my Roth-Runckenstein module(the recursive part). I shall be glad if you could send me your code or implementation details for the GS decoder and in particular the bivariate factoring step.The exposition of Prof McEliece is really great and also the average case analysis of list size was interesting.

Thanking You

Anand kumar

March 3, 2006 at 1:34 pm

elo..

i know that u must have strived really hard to implement this algorithm but i would really appreciate if you could please send me a copy of your lines of codes for the Guruswami Sudan Decoder..it is part of my final year project..i’ll try understand what you’ve done in Matlab and then implement it in C++..but you already have it for c++,can u please send it to me as soon as possible?

March 7, 2006 at 1:55 pm

elo dear commentors..plz note what Dr sarwat syas: “Apparently people who comment on this post are incapable or too lazy to follow links. I will not email you my code — just follow the link above. I have neither the time nor the inclination to deal with requests on an individual basis. If you can’t get it on your own, perhaps you should find some other job that doesn’t require you to use computers.” so dnt hope of getting anything here..

bye n good luk..

March 17, 2006 at 10:28 pm

Hi dear friends

Now I’m working on joint coding and cryptography for my class project. And I must wrote with Matlab or c++ (software) for it but unfortunately couldn’t success by now! If any one can help me on this field I’m much appreciated.

April 24, 2006 at 9:47 pm

Plz send me ur matlab code for RS encoder/decoder , thanks for you!

July 9, 2006 at 12:23 pm

could u mind sending me ur matlab program for encoding ldpc because i found a difficulty in transfer H from non systimatic to systimatic form.

many thanks

August 7, 2006 at 4:52 pm

Dear~~!

I’m studying about the DMB system.

and I hope to simulate that.

So.. I realy realy need the Reed-Solomon soureces(encoder / decoder).

Can I please have the RS m-file?

I’ll be waiting for ur response..

Help!! me~~ pleeee~~z!

Have a GOOD day~~! ♡

dduish@hotmail.com

August 23, 2006 at 9:27 pm

please try to send me reed solomon encodr/decoder matlab code .I have to implement a RS code.

Thanks

August 30, 2006 at 2:23 am

Can send me ur matlab code?

thanks

September 19, 2006 at 7:13 pm

hi sir,

please send me the matlab programs for decoding binary BCH codes (using berlekamp algorithm)

January 16, 2007 at 3:06 am

Hi,

can anyone plz send ‘c’ code for Guruswami-sudan decoder to my id karthikkoneru@yahoo.com

February 12, 2007 at 4:44 am

hi

sir iam working on reed solomon coding but iam not understanding maths and algorithm steps …so plz anybody help me …..if possible send ‘c’coding .

thanks in advance