jyisgreat / rs_matlab Goto Github PK

All this MATLAB 2011 code is my attempt to make simple Reed-Solomon coder/decoder over GF(2^m)
This implementation isn't designed to be FAST. My main consideration was:
			"readability >> optimization"

Therefore, it is really slow compared to RS decoders used in production :)

Brief description follows
GF related:
-gf_calculate_mt - compute multiplication table for finite field extension GF(2^m)
-gf_calculate_pt - compute powers and logarithms table for specified element from GF(2^m)

All following functions use powers table obtained from gf_calculate_pt()
gf_div, gf_mul - fast division and multiplication in GF(2^m)
gf_el_order - compute order of finite field element

Polynomials (all polymials are defined over GF(2^m), where m can be 1):
poly_div - division with remainder
poly_mul - multiplication
poly_sum - sum of polynomials
poly_eval - evaluate polynomial inf GF(2^m) at point X, X belongs to GF(2^m)
poly_nonzero - test polynomial for non-zeroness (similar to nnz())
poly_trim - trim highest powers with zero coefficients
poly_xn - construct polynomial p(x) = x^n
poly_diff - compute formal derivative p'(x) over GF(2^m)
poly_gcd - find greatest common divisor of polynomials using Euclid's algorithm

LFSR (LFSR stands for Linear Feedback Shift Register):
berlekamp - compute minimal LFSR that generates specified sequence using Berlekamp-Massey algorithm.
	Throws "division by 0" if first sequence element is zero!
lfsr_test - compute first N elements of sequence generated by supplied LFSR

Reed-Solomon:
rs_generator - compute RS over GF(2^m) generator polynomial which provides specified Dmin
rs_encode - systematically encode some data block (symbols are elements of GF(2^m)) in RS code
rs_decode - try to decode received RS code word and correct errors. Uses Berlekamp-Massey algorithm
	to compute locator polynomial L(x), Chien search to find its roots, and Forney algorithm
	to find exact error values.
rs_test - demonstrative test:
	random data -> encode -> +random errors -> decode -> test for data correctness

To see something that all this stuff can do, just run rs_test()

(C) Roman Dobrodiy