25485

Algorytm wyznaczania funkcji skrótu

W ogólnym przypadku znane są dwie procedury kodowania, zapewniające wydzielenie w ciągu kodowym poszczególnych sygnałów informacyjnych, tzn. otrzymanie kodu rozdzielnego. W procedurach tych przyjmuje się zwykle, że sygnały informacyjne występują na m bardziej znaczących pozycjach ciągu kodowego.

W pierwszej z omawianych procedur wykorzystuje się, że w tym przypadku część wielomianu kodowego opisującego sygnały informacyjne ma postać

s'(x) = x"-“ w(x) = x^k w(x)    (7)

gdzie w(x) oznacza wielomian informacyjny.

Wielomian kodowy przy założeniu (7) można przedstawić w postaci:

s(x) = w(x).x^k + s”(x) = x^k w(x) + s"(x)    (8)

gdzie: s”(x) - wielomian stopnia k-1.

Poniżej wyznacza się warunek jaki musi spełniać wielomian s' "OO , aby wielomian s(x) był wielomianem kodowym, tzn. aby był wielokrotnością wielomianu generującego <?(*)

s(x)

g(*)

= a(x)

Podstawiając do powyższej zależności wyrażenie (8) otrzymuje się

O)

w(x) -|-S"0)

<70)

Zatem

(9)

x*w(x) , . s"(x) —— = a(x) + ——

g(x) g(x)

Otrzymano zatem, że poszukiwany wielomian s"O0 jest resztą z dzielenia wielomianu    JKT^/x    przez wielomian generujący

g(*).

Zasada kodowania w omawianym przypadku ma postać:

s(x) =x*w(x)

w(x)

g(*)

(10)

Przykład: 1

Poniżej wyznacza się wielomian kodowy s( x) dla następujących danych : n=7, A=3, g(x)= x³ + x + 1

Uwzględniając, że n-m = k = 3 określa się wielomian

s’(x) = x^k w(x) = x³(x+l) = x⁴+x³

Dzieląc powyższy wielomian przez wielomian generujący otrzymuje się

_2Ł±1

x³+x+l

x⁴+x³    :

sit_x²+x

x³+x²+x _xVq -f _X+1 x²+    1