Reed-Solomon hata düzeltme - Reed–Solomon error correction

Reed – Solomon kodu bir [n, k, n − k + 1] kodu; başka bir deyişle, bu bir doğrusal blok kodu uzunluk n (bitmiş F) ile boyut k ve minimum Hamming mesafesi ${ textstyle d _ { min} = n-k + 1.}$ Reed-Solomon kodu, minimum mesafenin doğrusal bir boyut kodu için mümkün olan maksimum değere sahip olması açısından optimaldir (n, k); bu olarak bilinir Singleton bağlı. Böyle bir kod aynı zamanda ayrılabilir maksimum mesafe (MDS) kodu.

Bir Reed-Solomon kodunun hata düzeltme yeteneği, minimum mesafesiyle veya eşdeğer bir şekilde şu şekilde belirlenir: ${ displaystyle n-k}$, bloktaki fazlalık ölçüsü. Hata simgelerinin yerleri önceden bilinmiyorsa, bir Reed-Solomon kodu en fazla ${ displaystyle (n-k) / 2}$ hatalı semboller, yani bloğa eklenen fazlalık sembollerin yarısı kadar hatayı düzeltebilir. Bazen hata yerleri önceden bilinir (ör. "Yan bilgiler" demodülatör sinyal-gürültü oranları )-bunlara denir silmeler. Bir Reed – Solomon kodu (herhangi bir MDS kodu ) hataların iki katı kadar silme işlemini düzeltebilir ve herhangi bir hata ve silme kombinasyonu, ilişki 2 olduğu sürece düzeltilebilir.E + S ≤ n − k memnun, nerede ${ displaystyle E}$ hata sayısıdır ve ${ displaystyle S}$ bloktaki silme sayısıdır.

Reed-Solomon kodunun teorik BER performansı (N = 255, K = 233, QPSK, AWGN). Adım benzeri karakteristik.

Teorik hata sınırı, aşağıdaki formülle açıklanabilir: AWGN için kanal FSK:^[11]

${ displaystyle P_ {b} yaklaşık { frac {2 ^ {m-1}} {2 ^ {m} -1}} { frac {1} {n}} sum _ { ell = t + 1} ^ {n} ell {n seçin ell} P_ {s} ^ { ell} (1-P_ {s}) ^ {n- ell}}$

ve diğer modülasyon şemaları için:

${ displaystyle P_ {b} yaklaşık { frac {1} {m}} { frac {1} {n}} sum _ { ell = t + 1} ^ {n} ell {n seç ell} P_ {s} ^ { ell} (1-P_ {s}) ^ {n- ell}}$

nerede ${ displaystyle t = { frac {1} {2}} (d _ { min} -1)}$, ${ displaystyle P_ {s} = 1- (1-s) ^ {h}}$, ${ displaystyle h = { frac {m} { log _ {2} M}}}$, ${ displaystyle s}$ kodlanmamış AWGN durumunda sembol hata oranı ve ${ displaystyle M}$ modülasyon sırasıdır.

Reed-Solomon kodlarının pratik kullanımları için sonlu bir alan kullanmak yaygındır ${ displaystyle F}$ ile ${ displaystyle 2 ^ {m}}$ elementler. Bu durumda, her sembol bir ${ displaystyle m}$-bit değeri. Gönderen, veri noktalarını kodlanmış bloklar olarak gönderir ve kodlanmış bloktaki sembol sayısı ${ displaystyle n = 2 ^ {m} -1}$. Dolayısıyla, 8 bitlik semboller üzerinde çalışan bir Reed – Solomon kodu, ${ displaystyle n = 2 ^ {8} -1 = 255}$ blok başına sembol. (Bu, yaygınlığı nedeniyle çok popüler bir değerdir. bayt odaklı bilgisayar sistemleri.) numara ${ displaystyle k}$, ile ${ displaystyle k$, nın-nin veri bloktaki semboller bir tasarım parametresidir. Yaygın olarak kullanılan kod kodlamaları ${ displaystyle k = 223}$ sekiz bitlik veri sembolü artı 32 sekiz bitlik eşlik sembolü bir ${ displaystyle n = 255}$- sembol bloğu; bu bir ${ displaystyle (n, k) = (255,223)}$ kod ve blok başına 16'ya kadar sembol hatasını düzeltebilir.

Yukarıda tartışılan Reed-Solomon kod özellikleri, onları özellikle hataların meydana geldiği uygulamalar için çok uygun hale getirir. patlamalar. Bunun nedeni, bir semboldeki kaç bitin hatalı olduğunun kodun önemi olmamasıdır - eğer bir semboldeki birden fazla bit bozulursa, bu yalnızca tek bir hata olarak sayılır. Tersine, bir veri akışı, hata patlamaları veya eksikliklerle değil, rastgele tek bitli hatalarla karakterize edilirse, bir Reed-Solomon kodu, bir ikili koda kıyasla genellikle zayıf bir seçimdir.

Reed-Solomon kodu, tıpkı evrişimli kod, şeffaf bir koddur. Bu, kanal sembollerinin ters hat boyunca bir yerde, kod çözücüler çalışmaya devam edecektir. Sonuç, orijinal verilerin tersine çevrilmesi olacaktır. Ancak Reed-Solomon kodu, kod kısaltıldığında şeffaflığını kaybeder. Kısaltılmış bir koddaki "eksik" bitlerin, verilerin tamamlanıp tamamlanmadığına bağlı olarak sıfırlarla veya birlerle doldurulması gerekir. (Başka bir deyişle, semboller ters çevrilmişse, sıfır dolgusunun bir tek dolgulu olarak ters çevrilmesi gerekir.) Bu nedenle, verilerin anlamının (yani, doğru veya tamamlanmış) çözülmesi zorunludur. Reed-Solomon kod çözmeden önce.

Reed – Solomon kodunun döngüsel veya yapının ince detaylarına bağlı değildir. Reed ve Solomon'un kod sözcüklerinin bir polinomun değerleri olduğu orijinal görünümünde, değerlendirme noktalarının sırası kodu döngüsel yapacak şekilde seçilebilir. Özellikle, eğer ${ displaystyle alpha}$ bir ilkel kök Alanın ${ displaystyle F}$, sonra tanım gereği sıfır olmayan tüm elemanlar ${ displaystyle F}$ formu al ${ displaystyle alpha ^ {i}}$ için ${ displaystyle i {1, noktalar, q-1 }}$, nerede ${ displaystyle q = | F |}$. Her polinom ${ displaystyle p}$ bitmiş ${ displaystyle F}$ bir kod sözcüğüne yol açar ${ displaystyle (p ( alfa ^ {1}), noktalar, p ( alfa ^ {q-1}))}$. İşlevinden beri ${ displaystyle a mapsto p ( alpha a)}$ aynı derecede bir polinomdur, bu fonksiyon bir kod sözcüğüne yol açar ${ displaystyle (p ( alfa ^ {2}), noktalar, p ( alfa ^ {q}))}$; dan beri ${ displaystyle alpha ^ {q} = alpha ^ {1}}$ tutar, bu kod sözcüğü döngüsel sola kaydırma orijinal kod sözcüğünden türetilen ${ displaystyle p}$. Dolayısıyla, değerlendirme noktaları olarak bir dizi ilkel kök güçleri seçmek, orijinal görünümü Reed-Solomon kodunu döngüsel. BCH görünümündeki Reed-Solomon kodları her zaman döngüseldir, çünkü BCH kodları döngüseldir.

Uyarılar

Tasarımcıların Reed – Solomon kod bloklarının "doğal" boyutlarını kullanması gerekmez. "Kısaltma" olarak bilinen bir teknik, daha büyük bir koddan istenen herhangi bir boyutta daha küçük bir kod üretebilir. Örneğin, yaygın olarak kullanılan (255,223) kod, kaynak bloğun kullanılmayan kısmını 95 ikili sıfır ile doldurarak ve bunları iletmeyerek bir (160,128) koda dönüştürülebilir. Kod çözücüde, bloğun aynı kısmı yerel olarak ikili sıfırlarla yüklenir. Delsarte-Goethals-Seidel^[12] teorem kısaltılmış Reed-Solomon kodlarının bir uygulamasının bir örneğini gösterir. Kısaltmaya paralel olarak bilinen bir teknik delme kodlanmış eşlik simgelerinin bazılarının çıkarılmasına izin verir.

BCH görünümü kod çözücüleri

Bu bölümde açıklanan kod çözücüler, bir kod sözcüğünün BCH görünümünü bir katsayı dizisi olarak kullanır. Hem kodlayıcı hem de kod çözücü tarafından bilinen sabit bir üretici polinomu kullanırlar.

Peterson – Gorenstein – Zierler kod çözücü

Daniel Gorenstein ve Neal Zierler, Ocak 1960'ta Zierler tarafından MIT Lincoln Laboratuvarı raporunda ve daha sonra Haziran 1961'de bir makalede açıklanan bir kod çözücü geliştirdi.^[13] Gorenstein – Zierler kod çözücü ve BCH kodlarıyla ilgili ilgili çalışma bir kitapta anlatılmıştır. Hata Düzeltme Kodları tarafından W. Wesley Peterson (1961).^[14]

Formülasyon

İletilen mesaj, ${ displaystyle (c_ {0}, ldots, c_ {i}, ldots, c_ {n-1})}$, bir polinomun katsayıları olarak görülür s(x):

${ displaystyle s (x) = toplam _ {i = 0} ^ {n-1} c_ {i} x ^ {i}}$

Reed-Solomon kodlama prosedürünün bir sonucu olarak, s(x) oluşturucu polinom ile bölünebilir g(x):

${ displaystyle g (x) = prod _ {j = 1} ^ {n-k} (x- alpha ^ {j}),}$

nerede α ilkel bir köktür.

Dan beri s(x) jeneratörün bir katıdır g(x), tüm köklerini "miras aldığını" takip eder:

${ displaystyle s ( alfa ^ {j}) = 0, j = 1,2, ldots, n-k}$

İletilen polinom, bir hata polinomu ile geçiş sırasında bozulmuş e(x) alınan polinomu üretmek için r(x).

${ displaystyle r (x) = s (x) + e (x)}$

${ displaystyle e (x) = toplam _ {i = 0} ^ {n-1} e_ {i} x ^ {i}}$

nerede e_ben katsayısı ben-nin gücü x. Katsayı e_ben o gücünde hata yoksa sıfır olacaktır. x ve bir hata varsa sıfırdan farklıdır. Eğer varsa ν farklı güçlerdeki hatalar ben_k nın-nin x, sonra

${ displaystyle e (x) = toplam _ {k = 1} ^ { nu} e_ {i_ {k}} x ^ {i_ {k}}}$

Kod çözücünün amacı, hata sayısını bulmaktır (ν), hataların konumları (ben_k) ve bu konumlardaki hata değerleri (e_benk). Onlardan, e(x) hesaplanabilir ve buradan çıkarılabilir r(x) orijinal olarak gönderilen mesajı almak için s(x).

Sendrom kod çözme

Kod çözücü, polinomu belirli noktalarda alındığı şekliyle değerlendirerek başlar. Bu değerlendirmenin sonuçlarını "sendromlar" olarak adlandırıyoruz. S_j. Bunlar şu şekilde tanımlanır:

${ displaystyle { başlar {hizalı} S_ {j} & = r ( alpha ^ {j}) = s ( alpha ^ {j}) + e ( alpha ^ {j}) = 0 + e ( alpha ^ {j}) = e ( alpha ^ {j}), j = 1,2, ldots, nk & = sum _ {k = 1} ^ { nu} e_ {i_ {k }} left ( alpha ^ {j} sağ) ^ {i_ {k}} end {hizalı}}}$

Sendromlara bakmanın avantajı, mesaj polinomunun çıkmasıdır. Başka bir deyişle, sendromlar yalnızca hatayla ilgilidir ve iletilen mesajın gerçek içeriğinden etkilenmez. Sendromların tümü sıfırsa, algoritma burada durur ve mesajın aktarım sırasında bozulmadığını bildirir.

Hata bulucular ve hata değerleri

Kolaylık sağlamak için tanımlayın hata bulucular X_k ve hata değerleri Y_k gibi:

${ displaystyle X_ {k} = alpha ^ {i_ {k}}, Y_ {k} = e_ {i_ {k}}}$

Daha sonra sendromlar bu hata bulucular ve hata değerleri açısından şu şekilde yazılabilir:

${ displaystyle S_ {j} = toplam _ {k = 1} ^ { nu} Y_ {k} X_ {k} ^ {j}}$

Sendrom değerlerinin bu tanımı öncekine eşdeğerdir, çünkü ${ displaystyle ( alpha ^ {j}) ^ {i_ {k}} = alpha ^ {j * i_ {k}} = ( alpha ^ {i_ {k}}) ^ {j} = X_ {k } ^ {j}}$.

Sendromlar bir sistem verir n − k ≥ 2ν 2'deki denklemlerν bilinmeyenler, ancak bu denklem sistemi doğrusal değildir. X_k ve bariz bir çözümü yok. Ancak, X_k (aşağıya bakınız) biliniyorsa, sendrom denklemleri, aşağıdakiler için kolayca çözülebilen doğrusal bir denklem sistemi sağlar. Y_k hata değerleri.

${ displaystyle { begin {bmatrix} X_ {1} ^ {1} & X_ {2} ^ {1} & cdots & X _ { nu} ^ {1} X_ {1} ^ {2} ve X_ {2 } ^ {2} & cdots & X _ { nu} ^ {2} vdots & vdots && vdots X_ {1} ^ {nk} & X_ {2} ^ {nk} & cdots & X_ { nu} ^ {nk} end {bmatrix}} { begin {bmatrix} Y_ {1} Y_ {2} vdots Y _ { nu} end {bmatrix}} = { başlangıç ​​{bmatrix} S_ {1} S_ {2} vdots S_ {nk} end {bmatrix}}}$

Sonuç olarak sorun, X_k, çünkü o zaman en soldaki matris bilinecek ve denklemin her iki tarafı da tersiyle çarpılarak Y_k

Hataların konumlarının zaten bilindiği bu algoritmanın varyantında (bir hata olarak kullanıldığında) silme kodu ), bu son. Hata yerleri (X_k) başka bir yöntemle zaten bilinmektedir (örneğin, bir FM iletiminde, bit akışının net olmadığı veya parazitle üstesinden gelinen bölümler olasılıksal olarak frekans analizinden belirlenebilir). Bu senaryoda, ${ displaystyle n-k}$ hatalar düzeltilebilir.

Algoritmanın geri kalanı, hataları bulmaya hizmet eder ve şu değerlere kadar sendrom değerleri gerektirir: ${ displaystyle 2v}$, sadece ${ displaystyle v}$ şimdiye kadar kullanıldı. Bu nedenle, konumlarını bilmeden düzeltilebilecek kadar hata düzeltme sembolünün 2 kat daha fazla eklenmesi gerekir.

Hata bulucu polinomu

Doğrusal denklem sistemine yol açan doğrusal bir tekrarlama ilişkisi vardır. Bu denklemleri çözmek, bu hata konumlarını belirler X_k.

Tanımla hata bulma polinomu Λ (x) gibi

${ displaystyle Lambda (x) = prod _ {k = 1} ^ { nu} (1-xX_ {k}) = 1+ Lambda _ {1} x ^ {1} + Lambda _ {2 } x ^ {2} + cdots + Lambda _ { nu} x ^ { nu}}$

Λ'nin sıfırları (x) karşılıklı ${ displaystyle X_ {k} ^ {- 1}}$. Bu, yukarıdaki ürün gösterim yapısından kaynaklanır, çünkü ${ displaystyle x = X_ {k} ^ {- 1}}$ çarpılan terimlerden biri sıfır olacaktır ${ displaystyle (1-X_ {k} ^ {- 1} cdot X_ {k}) = 1-1 = 0}$, tüm polinomun sıfır olarak değerlendirilmesi.

${ displaystyle Lambda (X_ {k} ^ {- 1}) = 0}$

İzin Vermek ${ displaystyle j}$ herhangi bir tam sayı olabilir ki ${ displaystyle 1 leq j leq nu}$. İki tarafı da çarpın ${ displaystyle Y_ {k} X_ {k} ^ {j + nu}}$ ve yine de sıfır olacaktır.

${ displaystyle { begin {align} & Y_ {k} X_ {k} ^ {j + nu} Lambda (X_ {k} ^ {- 1}) = 0. & Y_ {k} X_ {k} ^ {j + nu} (1+ Lambda _ {1} X_ {k} ^ {- 1} + Lambda _ {2} X_ {k} ^ {- 2} + cdots + Lambda _ { nu} X_ {k} ^ {- nu}) = 0. & Y_ {k} X_ {k} ^ {j + nu} + Lambda _ {1} Y_ {k} X_ {k} ^ {j + nu } X_ {k} ^ {- 1} + Lambda _ {2} Y_ {k} X_ {k} ^ {j + nu} X_ {k} ^ {- 2} + cdots + Lambda _ { nu } Y_ {k} X_ {k} ^ {j + nu} X_ {k} ^ {- nu} = 0. & Y_ {k} X_ {k} ^ {j + nu} + Lambda _ {1 } Y_ {k} X_ {k} ^ {j + nu -1} + Lambda _ {2} Y_ {k} X_ {k} ^ {j + nu -2} + cdots + Lambda _ { nu } Y_ {k} X_ {k} ^ {j} = 0. uç {hizalı}}}$

Toplamı k = 1 ila ν ve yine de sıfır olacaktır.

${ displaystyle { begin {align} & sum _ {k = 1} ^ { nu} left (Y_ {k} X_ {k} ^ {j + nu} + Lambda _ {1} Y_ {k } X_ {k} ^ {j + nu -1} + Lambda _ {2} Y_ {k} X_ {k} ^ {j + nu -2} + cdots + Lambda _ { nu} Y_ {k } X_ {k} ^ {j} sağ) = 0 uç {hizalı}}}$

Her terimi kendi toplamında toplayın.

${ displaystyle { başla {hizalı} & sol ( toplamı _ {k = 1} ^ { nu} Y_ {k} X_ {k} ^ {j + nu} sağ) + sol ( toplamı _ {k=1}^{ u }Lambda _{1}Y_{k}X_{k}^{j+ u -1} ight)+left(sum _{k=1}^{ nu }Lambda _{2}Y_{k}X_{k}^{j+ u -2} ight)+cdots +left(sum _{k=1}^{ u }Lambda _ { u }Y_{k}X_{k}^{j} ight)=0end{aligned}}}$

Extract the constant values of ${ displaystyle Lambda}$ that are unaffected by the summation.

${displaystyle {egin{aligned}&left(sum _{k=1}^{ u }Y_{k}X_{k}^{j+ u } ight)+Lambda _{1}left(sum _{k=1}^{ u }Y_{k}X_{k}^{j+ u -1} ight)+Lambda _{2}left(sum _{k=1}^{ u }Y_{k}X_{k}^{j+ u -2} ight)+cdots +Lambda _{ u }left(sum _{k=1}^{ u }Y_{k}X_{k}^{j} ight)=0end{aligned}}}$

These summations are now equivalent to the syndrome values, which we know and can substitute in! This therefore reduces to

${displaystyle S_{j+ u }+Lambda _{1}S_{j+ u -1}+cdots +Lambda _{ u -1}S_{j+1}+Lambda _{ u }S_{j}=0,}$

Çıkarma ${displaystyle S_{j+ u }}$ from both sides yields

${displaystyle S_{j}Lambda _{ u }+S_{j+1}Lambda _{ u -1}+cdots +S_{j+ u -1}Lambda _{1}=-S_{j+ u } }$

Recall that j was chosen to be any integer between 1 and v inclusive, and this equivalence is true for any and all such values. Therefore, we have v linear equations, not just one. This system of linear equations can therefore be solved for the coefficients Λ_ben of the error location polynomial:

${displaystyle {egin{bmatrix}S_{1}&S_{2}&cdots &S_{ u }S_{2}&S_{3}&cdots &S_{ u +1}vdots &vdots &&vdots S_{ u }&S_{ u +1}&cdots &S_{2 u -1}end{bmatrix}}{egin{bmatrix}Lambda _{ u }Lambda _{ u -1}vdots Lambda _{1}end{bmatrix}}={egin{bmatrix}-S_{ u +1}-S_{ u +2}vdots -S_{ u + u }end{bmatrix}}}$

The above assumes the decoder knows the number of errors ν, but that number has not been determined yet. The PGZ decoder does not determine ν directly but rather searches for it by trying successive values. The decoder first assumes the largest value for a trial ν and sets up the linear system for that value. If the equations can be solved (i.e., the matrix determinant is nonzero), then that trial value is the number of errors. If the linear system cannot be solved, then the trial ν is reduced by one and the next smaller system is examined. (Gill n.d., s. 35)

Find the roots of the error locator polynomial

Use the coefficients Λ_ben found in the last step to build the error location polynomial. The roots of the error location polynomial can be found by exhaustive search. The error locators X_k are the reciprocals of those roots. The order of coefficients of the error location polynomial can be reversed, in which case the roots of that reversed polynomial are the error locators ${displaystyle X_{k}}$ (not their reciprocals ${displaystyle X_{k}^{-1}}$). Chien search is an efficient implementation of this step.

Calculate the error values

Once the error locators X_k are known, the error values can be determined. This can be done by direct solution for Y_k içinde error equations matrix given above, or using the Forney algorithm.

Calculate the error locations

Hesaplamak ben_k by taking the log base ${ displaystyle alpha}$ nın-nin X_k. This is generally done using a precomputed lookup table.

Fix the errors

Finally, e(x) is generated from ben_k ve e_benk and then is subtracted from r(x) to get the originally sent message s(x), with errors corrected.

Misal

Consider the Reed–Solomon code defined in GF(929) ile α = 3 ve t = 4 (this is used in PDF417 barcodes) for a RS(7,3) code. The generator polynomial is

${displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522}$

If the message polynomial is p(x) = 3 x² + 2 x + 1, then a systematic codeword is encoded as follows.

${displaystyle s_{r}(x)=p(x),x^{t}mod g(x)=547x^{3}+738x^{2}+442x+455}$

${displaystyle s(x)=p(x),x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474}$

Errors in transmission might cause this to be received instead.

${displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474}$

The syndromes are calculated by evaluating r at powers of α.

${displaystyle S_{1}=r(3^{1})=3cdot 3^{6}+2cdot 3^{5}+123cdot 3^{4}+456cdot 3^{3}+191cdot 3^{2}+487cdot 3+474=732}$

${displaystyle S_{2}=r(3^{2})=637,;S_{3}=r(3^{3})=762,;S_{4}=r(3^{4})=925}$

${displaystyle {egin{bmatrix}732&637637&762end{bmatrix}}{egin{bmatrix}Lambda _{2}Lambda _{1}end{bmatrix}}={egin{bmatrix}-762-925end{bmatrix}}={egin{bmatrix}167�04end{bmatrix}}}$

Kullanma Gauss elimine etme:

${displaystyle {egin{bmatrix}001&000�00&001end{bmatrix}}{egin{bmatrix}Lambda _{2}Lambda _{1}end{bmatrix}}={egin{bmatrix}329821end{bmatrix}}}$

Λ(x) = 329 x² + 821 x + 001, with roots x₁ = 757 = 3⁻³ and x₂ = 562 = 3⁻⁴

The coefficients can be reversed to produce roots with positive exponents, but typically this isn't used:

R(x) = 001 x² + 821 x + 329, with roots 27 = 3³ and 81 = 3⁴

with the log of the roots corresponding to the error locations (right to left, location 0 is the last term in the codeword).

To calculate the error values, apply the Forney algorithm.

Ω(x) = S(x) Λ(x) mod x⁴ = 546 x + 732

Λ'(x) = 658 x + 821

e₁ = −Ω(x₁)/Λ'(x₁) = 074

e₂ = −Ω(x₂)/Λ'(x₂) = 122

Çıkarma e₁ x³ ve e₂ x⁴ from the received polynomial r reproduces the original codeword s.

Berlekamp–Massey decoder

Berlekamp–Massey algorithm is an alternate iterative procedure for finding the error locator polynomial. During each iteration, it calculates a discrepancy based on a current instance of Λ(x) with an assumed number of errors e:

${displaystyle Delta =S_{i}+Lambda _{1} S_{i-1}+cdots +Lambda _{e} S_{i-e}}$

and then adjusts Λ(x) ve e so that a recalculated Δ would be zero. Makale Berlekamp–Massey algorithm has a detailed description of the procedure. In the following example, C(x) is used to represent Λ(x).

Misal

Using the same data as the Peterson Gorenstein Zierler example above:

The final value of C is the error locator polynomial, Λ(x).

Euclidean decoder

Another iterative method for calculating both the error locator polynomial and the error value polynomial is based on Sugiyama's adaptation of the extended Euclidean algorithm .

Define S(x), Λ(x), and Ω(x) for t syndromes and e hatalar:

${displaystyle S(x)=S_{t}x^{t-1}+S_{t-1}x^{t-2}+cdots +S_{2}x+S_{1}}$

${displaystyle Lambda (x)=Lambda _{e}x^{e}+Lambda _{e-1}x^{e-1}+cdots +Lambda _{1}x+1}$

${displaystyle Omega (x)=Omega _{e}x^{e}+Omega _{e-1}x^{e-1}+cdots +Omega _{1}x+Omega _{0}}$

The key equation is:

${displaystyle Lambda (x)S(x)=Q(x)x^{t}+Omega (x)}$

İçin t = 6 and e = 3:

${displaystyle {egin{bmatrix}Lambda _{3}S_{6}&x^{8}Lambda _{2}S_{6}+Lambda _{3}S_{5}&x^{7}Lambda _{1}S_{6}+Lambda _{2}S_{5}+Lambda _{3}S_{4}&x^{6}S_{6}+Lambda _{1}S_{5}+Lambda _{2}S_{4}+Lambda _{3}S_{3}&x^{5}S_{5}+Lambda _{1}S_{4}+Lambda _{2}S_{3}+Lambda _{3}S_{2}&x^{4}S_{4}+Lambda _{1}S_{3}+Lambda _{2}S_{2}+Lambda _{3}S_{1}&x^{3}S_{3}+Lambda _{1}S_{2}+Lambda _{2}S_{1}&x^{2}S_{2}+Lambda _{1}S_{1}&xS_{1}end{bmatrix}}={egin{bmatrix}Q_{2}x^{8}Q_{1}x^{7}Q_{0}x^{6}���Omega _{2}x^{2}Omega _{1}xOmega _{0}end{bmatrix}}}$

The middle terms are zero due to the relationship between Λ and syndromes.

The extended Euclidean algorithm can find a series of polynomials of the form

Bir_ben(x) S(x) + B_ben(x) x^t = R_ben(x)

where the degree of R decreases as ben artışlar. Once the degree of R_ben(x) < t/ 2, sonra

Bir_ben(x) = Λ(x)

B_ben(x) = −Q(x)

R_ben(x) = Ω(x).

B(x) and Q(x) don't need to be saved, so the algorithm becomes:

R₋₁ = x^t

R₀ = S(x)

Bir₋₁ = 0

Bir₀ = 1

i = 0

while degree of R_ben ≥ t/2

i = i + 1

Q = R_i-2 / R_i-1

R_ben = R_i-2 - Q R_i-1

Bir_ben = A_i-2 - Q A_i-1

to set low order term of Λ(x) to 1, divide Λ(x) and Ω(x) by A_ben(0):

Λ(x) = A_ben / A_ben(0)

Ω(x) = R_ben / A_ben(0)

Bir_ben(0) is the constant (low order) term of A_ben.

Misal

Using the same data as the Peterson–Gorenstein–Zierler example above:

Λ(x) = A₂ / 544 = 329 x² + 821 x + 001

Ω(x) = R₂ / 544 = 546 x + 732

Decoder using discrete Fourier transform

A discrete Fourier transform can be used for decoding.^[15] To avoid conflict with syndrome names, let c(x) = s(x) the encoded codeword. r(x) ve e(x) are the same as above. Tanımlamak C(x), E(x), ve R(x) as the discrete Fourier transforms of c(x), e(x), ve r(x). Dan beri r(x) = c(x) + e(x), and since a discrete Fourier transform is a linear operator, R(x) = C(x) + E(x).

Dönüştürme r(x) için R(x) using discrete Fourier transform. Since the calculation for a discrete Fourier transform is the same as the calculation for syndromes, t coefficients of R(x) ve E(x) are the same as the syndromes:

${displaystyle R_{j}=E_{j}=S_{j}=r(alpha ^{j})}$

${displaystyle { ext{for }}1leq jleq t}$

Kullanım ${ displaystyle R_ {1}}$ vasıtasıyla ${displaystyle R_{t}}$ as syndromes (they're the same) and generate the error locator polynomial using the methods from any of the above decoders.

Let v = number of errors. Generate E(x) using the known coefficients ${displaystyle E_{1}}$ -e ${displaystyle E_{t}}$, the error locator polynomial, and these formulas

${displaystyle E_{0}=-{frac {1}{Lambda _{v}}}(E_{v}+Lambda _{1}E_{v-1}+cdots +Lambda _{v-1}E_{1})}$

${displaystyle E_{j}=-(Lambda _{1}E_{j-1}+Lambda _{2}E_{j-2}+cdots +Lambda _{v}E_{j-v})}$

${displaystyle { ext{for }}t$

Then calculate C(x) = R(x) − E(x) and take the inverse transform (polynomial interpolation) of C(x) to produce c(x).

Decoding beyond the error-correction bound

Singleton bound states that the minimum distance d of a linear block code of size (n,k) is upper-bounded by n − k + 1. The distance d was usually understood to limit the error-correction capability to ⌊d/2⌋. The Reed–Solomon code achieves this bound with equality, and can thus correct up to ⌊(n − k + 1)/2⌋ errors. However, this error-correction bound is not exact.

1999 yılında Madhu Sudan ve Venkatesan Guruswami at MIT published "Improved Decoding of Reed–Solomon and Algebraic-Geometry Codes" introducing an algorithm that allowed for the correction of errors beyond half the minimum distance of the code.^[16] It applies to Reed–Solomon codes and more generally to algebraic geometric codes. This algorithm produces a list of codewords (it is a list-decoding algorithm) and is based on interpolation and factorization of polynomials over ${displaystyle GF(2^{m})}$ and its extensions.

Soft-decoding

The algebraic decoding methods described above are hard-decision methods, which means that for every symbol a hard decision is made about its value. For example, a decoder could associate with each symbol an additional value corresponding to the channel demodülatör 's confidence in the correctness of the symbol. Gelişi LDPC ve turbo codes, which employ iterated soft-decision belief propagation decoding methods to achieve error-correction performance close to the theoretical limit, has spurred interest in applying soft-decision decoding to conventional algebraic codes. In 2003, Ralf Koetter and Alexander Vardy presented a polynomial-time soft-decision algebraic list-decoding algorithm for Reed–Solomon codes, which was based upon the work by Sudan and Guruswami.^[17]In 2016, Steven J. Franke and Joseph H. Taylor published a novel soft-decision decoder.^[18]

Matlab example

Encoder

Here we present a simple Matlab implementation for an encoder.

işlevi[encoded] =rsEncoder(msg, m, prim_poly, n, k)% RSENCODER Encode message with the Reed-Solomon algorithm    % m is the number of bits per symbol    % prim_poly: Primitive polynomial p(x). Ie for DM is 301    % k is the size of the message    % n is the total size (k+redundant)    % Example: msg = uint8('Test')    % enc_msg = rsEncoder(msg, 8, 301, 12, numel(msg));     % Get the alpha    alfa = gf(2, m, prim_poly);     % Get the Reed-Solomon generating polynomial g(x)    g_x = genpoly(k, n, alfa);     % Multiply the information by X^(n-k), or just pad with zeros at the end to    % get space to add the redundant information    msg_padded = gf([msg sıfırlar(1, n - k)], m, prim_poly);     % Get the remainder of the division of the extended message by the    % Reed-Solomon generating polynomial g(x)    [~, kalan] = deconv(msg_padded, g_x);     % Now return the message with the redundant information    kodlanmış = msg_padded - kalan;son% Find the Reed-Solomon generating polynomial g(x), by the way this is the% same as the rsgenpoly function on matlabişlevig =genpoly(k, n, alpha)g = 1;    % A multiplication on the galois field is just a convolution    için k = mod(1 : n - k, n)        g = conv(g, [1 alfa .^ (k)]);    sonson

Decoder

Now the decoding part:

işlevi[decoded, error_pos, error_mag, g, S] =rsDecoder(encoded, m, prim_poly, n, k)% RSDECODER Decode a Reed-Solomon encoded message    %   Example:    % [dec, ~, ~, ~, ~] = rsDecoder(enc_msg, 8, 301, 12, numel(msg))    max_errors = zemin((n - k) / 2);    orig_vals = kodlanmış.x;    % Initialize the error vector    hatalar = sıfırlar(1, n);    g = [];    S = [];     % Get the alpha    alfa = gf(2, m, prim_poly);     % Find the syndromes (Check if dividing the message by the generator    % polynomial the result is zero)    Synd = polyval(kodlanmış, alfa .^ (1:n - k));    Sendromlar = kırpmak(Synd);     % If all syndromes are zeros (perfectly divisible) there are no errors    Eğer isempty(Syndromes.x)        decoded = orig_vals(1:k);        error_pos = [];        error_mag = [];        g = [];        S = Synd;        dönüş;    son% Prepare for the euclidean algorithm (Used to find the error locating    % polynomials)    r0 = [1, sıfırlar(1, 2 * max_errors)]; r0 = gf(r0, m, prim_poly); r0 = kırpmak(r0);    size_r0 = uzunluk(r0);    r1 = Sendromlar;    f0 = gf([sıfırlar(1, size_r0 - 1) 1], m, prim_poly);    f1 = gf(sıfırlar(1, size_r0), m, prim_poly);    g0 = f1; g1 = f0;     % Do the euclidean algorithm on the polynomials r0(x) and Syndromes(x) in    % order to find the error locating polynomial    süre doğru        % Do a long division        [bölüm, kalan] = deconv(r0, r1);        % Add some zeros        bölüm = pad(bölüm, uzunluk(g1));             % Find quotient*g1 and pad        c = conv(bölüm, g1);        c = kırpmak(c);        c = pad(c, uzunluk(g0));             % Update g as g0-quotient*g1        g = g0 - c;             % Check if the degree of remainder(x) is less than max_errors        Eğer all(remainder(1:end - max_errors) == 0)            kırmak;        son% Update r0, r1, g0, g1 and remove leading zeros        r0 = kırpmak(r1); r1 = kırpmak(kalan);        g0 = g1; g1 = g;    son% Remove leading zeros    g = kırpmak(g);     % Find the zeros of the error polynomial on this galois field    evalPoly = polyval(g, alfa .^ (n - 1 : - 1 : 0));    error_pos = gf(bulmak(evalPoly == 0), m);     % If no error position is found we return the received work, because    % basically is nothing that we could do and we return the received message    Eğer isempty(error_pos)        decoded = orig_vals(1:k);        error_mag = [];        dönüş;    son% Prepare a linear system to solve the error polynomial and find the error    % magnitudes    size_error = uzunluk(error_pos);    Syndrome_Vals = Sendromlar.x;    b(:, 1) = Syndrome_Vals(1:size_error);    için idx = 1 : size_error        e = alfa .^ (idx * (n - error_pos.x));        hata = e.x;        ee(idx, :) = hata;    son% Solve the linear system    error_mag = (gf(ee, m, prim_poly) \ gf(b, m, prim_poly))';    % Put the error magnitude on the error vector    hatalar(error_pos.x) = error_mag.x;    % Bring this vector to the galois field    errors_gf = gf(hatalar, m, prim_poly);     % Now to fix the errors just add with the encoded code    decoded_gf = kodlanmış(1:k) + errors_gf(1:k);    decoded = decoded_gf.x;son% Remove leading zeros from Galois arrayişlevigt =kırpmak(g)gx = g.x;    gt = gf(gx(bulmak(gx, 1) : son), g.m, g.prim_poly);son% Add leading zerosişlevixpad =pad(x, k)len = uzunluk(x);    Eğer (len < k)        xpad = [sıfırlar(1, k - len) x];    sonson

Reed Solomon original view decoders

The decoders described in this section use the Reed Solomon original view of a codeword as a sequence of polynomial values where the polynomial is based on the message to be encoded. The same set of fixed values are used by the encoder and decoder, and the decoder recovers the encoding polynomial (and optionally an error locating polynomial) from the received message.

Theoretical decoder

Reed & Solomon (1960) described a theoretical decoder that corrected errors by finding the most popular message polynomial. The decoder only knows the set of values ${ displaystyle a_ {1}}$ -e ${displaystyle a_{n}}$ and which encoding method was used to generate the codeword's sequence of values. The original message, the polynomial, and any errors are unknown. A decoding procedure could use a method like Lagrange interpolation on various subsets of n codeword values taken k at a time to repeatedly produce potential polynomials, until a sufficient number of matching polynomials are produced to reasonably eliminate any errors in the received codeword. Once a polynomial is determined, then any errors in the codeword can be corrected, by recalculating the corresponding codeword values. Unfortunately, in all but the simplest of cases, there are too many subsets, so the algorithm is impractical. The number of subsets is the binom katsayısı, ${displaystyle extstyle {inom {n}{k}}={n! over (n-k)!k!}}$, and the number of subsets is infeasible for even modest codes. Bir ${displaystyle (255,249)}$ code that can correct 3 errors, the naive theoretical decoder would examine 359 billion subsets.

Berlekamp Welch decoder

In 1986, a decoder known as the Berlekamp–Welch algorithm orijinal mesaj polinomunu kurtarabilen bir kod çözücü ve aynı zamanda hatalara karşılık gelen girdi değerleri için sıfırlar üreten bir hata "yer belirleyici" polinomu olarak geliştirilmiştir, zaman karmaşıklığı O (n ^ 3) ile burada n sayıdır bir mesajdaki değerlerin Kurtarılan polinom daha sonra orijinal mesajı kurtarmak için (gerektiğinde yeniden hesaplayın) kullanılır.

Misal

RS (7,3), GF (929) ve değerlendirme noktaları kümesini kullanma a_ben = ben − 1

a = {0, 1, 2, 3, 4, 5, 6}

Mesaj polinomu ise

p(x) = 003 x² + 002 x + 001

Kod sözcüğü

c = {001, 006, 017, 034, 057, 086, 121}

İletimdeki hatalar bunun yerine bunun alınmasına neden olabilir.

b = c + e = {001, 006, 123, 456, 057, 086, 121}

Anahtar denklemler:

${ displaystyle b_ {i} E (a_ {i}) - Q (a_ {i}) = 0}$

Maksimum hata sayısını varsayın: e = 2. Anahtar denklemler şu hale gelir:

${ displaystyle b_ {i} (e_ {0} + e_ {1} a_ {i}) - (q_ {0} + q_ {1} a_ {i} + q_ {2} a_ {i} ^ {2} + q_ {3} a_ {i} ^ {3} + q_ {4} a_ {i} ^ {4}) = - b_ {i} a_ {i} ^ {2}}$

${ Displaystyle { ucu {bmatrix}} {başlar } {001 ve 000 ve 928 ve 000 ve 000 ve 000 ve 000 006 ve 006 ve 928 ve 928 ve 928 ve 928 ve 928 123 ve 246 ve 928 ve 927 ve 925 ve 921 ve 913 456 ve 439 ve 928 ve 926 ve 920 ve 902 ve 848 057 ve 228 ve 928 ve 925 ve 913 ve 865 ve 673 086 ve 430 ve 928 ve 924 ve 904 ve 804 ve 304 121 ve 726 ve 928 ve 923 ve 893 ve 713 ve 562 bmatrix başlar {bmatrix} e_ {0} e_ {1} q_ {0} q_ {1} q_ {2} q_ {3} q_ {4} end {bmatrix}} = { begin {bmatrix} 000 923 437 541 017 637 289 end {bmatrix}}}$

Kullanma Gauss elimine etme:

${ displaystyle { begin {bmatrix} 001 & 000 & 000 & 000 & 000 & 000 & 000 000 & 001 & 000 & 000 & 000 & 000 000 & 000 & 001 & 000 & 000 & 000 & 000 000 & 000 & 000 & 000 & 001 & 000 & 000 & 000 & 000 & 000 & 000 & 000 & 000 {001 & 000 & 000 & 000 & 000 & 000 & 000 & 000 {001 & 000 & 000 & 000 & 000 & 000 & 000} q_ {0} q_ {1} q_ {2} q_ {3} q_ {4} end {bmatrix}} = { begin {bmatrix} 006 924 006 007 009 916 003 end {bmatrix}}}$