2749771993

Kody wykrywające i korygujące błędy - konspekt wykładu 2006/07    11

2 Kody liniowe

Niech I_m G M™ oznacza macierz jednostkową o wyrazach z ciała GF(q).

Najbardziej praktyczne w zastosowaniach i łatwe w zrozumieniu są kody liniowe, czyli kody w których słowa kodowe tworzą podprzestrzeń wektorową.

Definicja 2.1. (n,k)-kodem liniowym nad ciałem GF(q) nazywamy k-wymiarową podprzestrzeń n-wymiarowej przestrzeni GF{q)ⁿ.

Proces kodowania

Wektor v G GF{q)ⁿ jest słowem kodowym (n, /c)-kodu liniowego wtw, gdy jest kombinacją liniową wektorów pewnej bazy przestrzeni k-wymiarowej. Stąd {n,k)~kod liniowy C = {Gu^T\u G GF(q)^k}, gdzie G G M^k jest pewną macierzą o wyrazach należących do ciała GF(q).

Definicja 2.2. Macierz, której kolumny są wektorami bazowymi k-wymiarowej podprzestrzeni C nazywamy macierzą kodującą lub macierzą generującą (n, k)-kodu linowego C.

Ponieważ podprzestrzeń może mieć więcej niż jedną bazę zatem również kod liniowy może mieć więcej niż jedną macierz generującą.

Powiemy, że macierz kodująca G jest w postaci standardowej, jeśli G = G M^k, gdzie P G M^k__k. Wówczas w każdym słowie kodowym v = V\... v_n G C pierwszych k symboli to symbole wysyłanej informacji u = ui.. .Uk, natomiast pozostałe n — k symboli to symbole sprawdzające, będące funkcją symboli informacji:

Vi = Ui,

Vk - u_k,

k

"fc+1 = ~Y.Pu^Ui’    (²)

k

Vn = ~

i= 1