Kod grupy

W teorii kodowania ( informatyka ) kod grupowy jest specjalnym kodowaniem, którego można używać do wykrywania i korygowania błędów . Do kodowania używana jest grupa (struktura algebraiczna).

Kodowanie

Kod grupowy jest kodem blokowym , co oznacza, że ​​wszystkie słowa kodowe mają taką samą długość (w dalszej części określamy długość słów kodowych ). ${\ displaystyle n}$

Dowolna grupa abelową jest stosowany jako alfabetu kodowania , zazwyczaj do cyklicznej grupy z rzędu drugiego, a oba elementy mogą być identyfikowane z bitami 0 i 1. ${\ displaystyle (A, {\ mathord {+}})}$${\ Displaystyle (\ {0,1 \}, {\ mathord {+}})}$

Te źródła zakodowane słowa są elementy grupy . (Wszystkie słowa z symbolami od długości ) ${\ Displaystyle (A, {\ mathord {+}}) ^ {k}}$${\ displaystyle A}$${\ displaystyle k}$

Do zakodowania grupy wybrano iniekcyjny homomorfizm . Obraz jest podzbiorem z . ${\ Displaystyle (A, {\ mathord {+}}) ^ {k}}$ ${\ displaystyle f \ colon (A, {\ mathord {+}}) ^ {k} \ to (A, {\ mathord {+}}) ^ {n}}$${\ displaystyle f}$${\ displaystyle (C, {\ mathord {+}})}$${\ Displaystyle (A, {\ mathord {+}}) ^ {n}}$

${\ displaystyle C}$to kod grupy. powiązana funkcja kodowania. ${\ displaystyle f}$

W przeciwieństwie do kodowania „arbitralnego”, każde słowo kodowe nie musi być osobno określane (przechowywane), ale wystarczy zdefiniować układ generujący grupę . Kodowanie pozostałych elementów można następnie obliczyć, używając ich reprezentacji jako sumy elementów generujących. ${\ displaystyle f}$${\ displaystyle f}$${\ Displaystyle (A, {\ mathord {+}}) ^ {k}}$

Przykłady

Przykład 1

Grupa ${\ Displaystyle (\ {0,1 \}, {\ mathord {+}})}$

Kodowanie źródłowe: ${\ Displaystyle (\ {0,1 \}, {\ mathord {+}}) ^ {3}}$

System generowania: , ,${\ Displaystyle e_ {1} = (1,0,0)}$${\ Displaystyle e_ {2} = (0, 1, 0)}$${\ Displaystyle e_ {3} = (0,0,1)}$

Kodowanie: , ,${\ Displaystyle f (e_ {1}) = (1, 1, 0, 0, 0)}$${\ Displaystyle f (e_ {2}) = (0,0,1,1,0)}$${\ Displaystyle f (e_ {3}) = (1, 0,1,0,1)}$

Teraz bądź słowem w kodowaniu źródłowym. Aby obliczyć kodowanie , wykonaj następujące czynności: ${\ Displaystyle c = (1,0,1)}$${\ displaystyle f (c)}$

Jeden reprezentuje jako sumę elementów generujących:${\ displaystyle c}$${\ Displaystyle c = (1,0,1) = e_ {1} + e_ {3}}$

a następnie oblicza sumę kodów tego samego ${\ Displaystyle f (c) = f (e_ {1}) + f (e_ {3}) = (1,1,0,0,0) + (1,0,1,0,1) = (0 , 1, 1, 0, 1)}$

Przykład 2

Grupa , czteroosobowa grupa Kleina${\ Displaystyle (\ {0,1, x, x + 1 \}, {\ mathord {+}})}$

Kodowanie źródłowe: ${\ Displaystyle (\ {0,1, x, x + 1 \}, {\ mathord {+}}) ^ {2}}$

System generowania: , , ,${\ Displaystyle e_ {1} = (1,0)}$${\ Displaystyle e_ {2} = (x, 0)}$${\ Displaystyle e_ {3} = (0,1)}$${\ Displaystyle e_ {4} = (0, x)}$

Kodowanie: , , ,${\ Displaystyle f (e_ {1}) = (1, 0, 0)}$${\ Displaystyle f (e_ {2}) = (1, 1, 0)}$${\ Displaystyle f (e_ {3}) = (x, 1,1)}$${\ Displaystyle f (e_ {4}) = (0,0, x)}$

Teraz bądź słowem w kodowaniu źródłowym. , , ${\ Displaystyle c = (1, x + 1)}$${\ displaystyle c = e_ {1} + e_ {3} + e_ {4}}$${\ Displaystyle f (c) = f (e_ {1}) + f (e_ {3}) + f (e_ {4}) = (1,0,0) + (x, 1,1) + (0 , 0, x) = (x + 1,1, x + 1)}$

cechy

Kody grup mają następujące właściwości:

• Słowa kodowe tworzą grupę
• W przypadku binarnego kodu grupowego rozkład odległości jest taki sam dla wszystkich słów kodowych, a także taki sam jak rozkład masy.
• Każdy kod grupy zawiera „ wektor zerowy ” jako prawidłowe słowo kodowe.
• Waga kodu grupy jest definiowana jako najmniejsza waga słowa kodowego ( waga Hamminga ) poza wagą wektora zerowego.
• W przypadku binarnych kodów grupowych odległość Hamminga odpowiada wadze kodu.

Zobacz też

• Kod liniowy jest kodowanie w którym skończonego są używane zamiast grupy .