Ograniczenie singletona

W teorii kodowania granica Singletona , nazwana na cześć Richarda Colloma Singletona, jest stosunkowo prymitywną górną granicą rozmiaru dowolnego kodu blokowego o $displaystyle n}$ bloku $,$ rozmiar ${\ displaystyle M }$ i minimalna odległość ${\ displaystyle d}$ . Jest również znany jako Joshibound . udowodnił Joshi (1958) , a jeszcze wcześniej Komamiya (1953) .

Oświadczenie związane

Minimalna odległość zbioru słów kodowych o długości $\ displaystyle$ zdefiniowana jako do $C }$

$${\ Displaystyle d = \ min _ {\ {x, y \ w C: x \ neq y \}} d (x, y )}$$

gdzie $y$ odległość między y $.$ _ $_$ _ Za ${\ Displaystyle A_ {q} (n, d)}$ reprezentuje maksymalną liczbę możliwych słów kodowych w blokowym kodzie o długości $displaystyle$$n}$ i minimalna odległość ${\ displaystyle re}$ .

Wtedy granica Singletona to stwierdza

$${\ Displaystyle A_ {q} (n, d) \ równoważnik q ^ {nd + 1}.}$$

Dowód

Najpierw zauważ, że liczba -arnych słów o długości wynosi ${\ displaystyle q$${\$$displaystyle q ^ {n}}$ , ponieważ każda litera w takim słowie może zająć jedną z $displaystyle q}$${n}$ różne wartości, niezależnie od pozostałych liter.

Niech teraz będzie dowolnym kodem blokowym o minimalnej odległości $q$$}$$displaystyle$ . Oczywiście wszystkie $słowa$ . Jeśli przebijemy kod, usuwając pierwsze $\$ słowa kodowego, wszystkie wynikowe słowa kodowe nadal muszą być parami różne, ponieważ wszystkie oryginalne słowa kodowe w do { $}$ mieć odległość Hamminga $.$ najmniej od siebie Tak więc rozmiar zmienionego kodu jest taki sam jak oryginalnego kodu.

Każde z nowo uzyskanych słów kodowych ma długość

$${\ Displaystyle n- (d-1) = nd + 1,}$$

ich najwyżej ${\ displaystyle q ^ {nd + 1}} .$ Ponieważ było to dowolne, to ograniczenie musi obowiązywać dla największego możliwego kodu z tymi parametrami, a zatem: do $\ displaystyle C}$

$${\ Displaystyle | C | \ równoważnik A_ {q} (n, d) \ równoważnik q ^ {nd + 1}.}$$

Kody liniowe

Jeśli jest kodem liniowym $o$${$ bloku , wymiarze i minimalnej odległości skończonym polem z $, do$$\$$}$ wtedy maksymalna liczba słów kodowych wynosi ${\ displaystyle q ^ {k}},$ a ograniczenie Singletona implikuje: q k {\ displaystyle q ^ {k}}

$${\ Displaystyle q ^ {k} \ równoważnik q ^ {nd + 1},}$$

aby

$${\ Displaystyle k \ równoważnik n-d + 1,}$$

który jest zwykle zapisywany jako

$${\ Displaystyle d \ równoważnik nk + 1.}$$

W przypadku kodu liniowego inny dowód ograniczenia Singletona można uzyskać, obserwując, że rząd macierzy kontroli parzystości wynosi ${\ displaystyle nk}$ . Kolejny prosty dowód wynika z obserwacji, że wiersze dowolnej macierzy generatora w standardowej postaci mają wagę co najwyżej ${\ displaystyle nk + 1}$ .

Historia

Zwykłym cytatem podanym dla tego wyniku jest Singleton (1964) , ale zostało to udowodnione wcześniej przez Joshiego (1958) . Według Welsha (1988 , s. 72) wynik można znaleźć w artykule Komamiyi z 1953 roku (1953)

kody MDS

Liniowe kody blokowe, które osiągają równość w powiązaniu Singletona, nazywane są kodami MDS (maksymalna separacja odległości) . Przykłady takich kodów obejmują kody, które mają tylko $mathbb {F} _ {q}}$ słowo all- $\ Displaystyle x \ in$$,$ mające zatem minimalna odległość ${\ Displaystyle n}$ ), kody, które wykorzystują całość ${\ Displaystyle (\ mathbb {F} _ {q}) ^ {n}}$ (minimalna odległość 1), kody z pojedynczym symbolem parzystości (minimalna odległość 2) i ich podwójne kody . Są one często nazywane trywialnymi kodami MDS.

W przypadku alfabetów binarnych istnieją tylko trywialne kody MDS.

Przykłady nietrywialnych kodów MDS obejmują kody Reeda-Solomona i ich rozszerzone wersje.

$są$ ważną klasą kodów blokowych, ponieważ dla stałego $.$ największe możliwości korekcji i wykrywania błędów Istnieje kilka sposobów charakteryzowania kodów MDS:

Twierdzenie - Niech $\ displaystyle n, k, d$ kodem liniowym nad kodem $}$ [ $}$ . Następujące są równoważne:

• $do {\ displaystyle C}$ kodem MDS.
• Dowolne $_$ macierzy generatora dla $_$ liniowo niezależne .
• Dowolne $parzystości$ macierzy dla $liniowo$ . _
• ${\ perp}}$ jest kodem MDS.
• Jeśli $macierzą$$generatora$ dla w standardowej formie $,$ podmacierz liczby pojedynczej
• Biorąc pod uwagę dowolne pozycje $współrzędnych$ , istnieje słowo kodowe (minimalna waga), którego są właśnie te pozycje.

Ostatnia z tych charakterystyk pozwala, przy użyciu tożsamości MacWilliamsa , na wyraźną formułę pełnego rozkładu wagi kodu MDS.

Twierdzenie - Niech $\ displaystyle \ mathbb {F} _ {q}}$ liniowym [ ${\ displaystyle n, k, d}$$fa$ q . Jeśli $to$ liczbę słów kodowych w wadze $A_ {$ ZA $}}$

$${\ Displaystyle A_ {w} = {\ binom {n} {w}} \ suma _ {j = 0} ^ {wd} (-1) ^ {j} {\ binom {w} {j}} (q ^{w-d+1-j}-1)={\binom {n}{w}}(q-1)\sum _{j=0}^{wd}(-1)^{j}{ \binom {w-1}{j}}q^{wdj}.}$$

Łuki w geometrii rzutowej

Liniowa niezależność kolumn macierzy generatora kodu MDS pozwala na konstruowanie kodów MDS z obiektów w skończonej geometrii rzutowej . Niech $}$$\ mathbb {F} _ { q}}$ będzie skończoną przestrzenią rzutową wymiaru (geometrycznego) nad polem skończonym $Displaystyle$ . Niech $rzutowej$ zbiorem punktów w przestrzeni . Utwórz $_$$której$ kolumny _ Następnie,

Twierdzenie - jest $za$ (przestrzennym) $\ displaystyle m}$ -arc ${$ wtedy i tylko wtedy, gdy macierzą generatora an $\ displaystyle [m, N + 1, mN]}$ Kod MDS na ${\ Displaystyle \ mathbb {F} _ {q}}$ .

Zobacz też

• Gilbert – Warszamow związany
• Związany z Plotkinem
• Hamming związany
• Johnson związany
• Związany z Griesmerem

Notatki

• Joshi, DD (1958), „Uwaga dotycząca górnych granic dla kodów minimalnej odległości”, Information and Control , 1 (3): 289–295, doi : 10.1016 / S0019-9958 (58) 80006-6
• Komamiya, Y. (1953), „Zastosowanie matematyki logicznej do teorii informacji”, Proc. 3. Japonia. Nat. Kong. Aplikacja Matematyka : 437
•   Ling, San; Xing, Chaoping (2004), Teoria kodowania / pierwszy kurs , Cambridge University Press, ISBN 0-521-52923-9
•   MacWilliams, FJ ; Sloane, NJA (1977), Teoria kodów korekcji błędów , North-Holland, s. 33, 37 , ISBN 0-444-85193-3
•   Pless, Vera (1998), Wprowadzenie do teorii kodów korygujących błędy (wyd. 3), Wiley Interscience, ISBN 0-471-19047-0
•   Roman, Steven (1992), Teoria kodowania i informacji , GTM , tom. 134, Springer-Verlag, ISBN 0-387-97812-7
• Singleton, RC (1964), „Kody q-nary maksymalnej odległości”, IEEE Trans. Inf. Teoria , 10 (2): 116–118, doi : 10.1109/TIT.1964.1053661
• Vermani, LR (1996), Elementy teorii kodowania algebraicznego , Chapman i Hall
•   Welsh, Dominic (1988), Kody i kryptografia , Oxford University Press, ISBN 0-19-853287-3

Dalsza lektura

•   JH van Lint (1992). Wprowadzenie do teorii kodowania . GTM . Tom. 86 (wyd. 2). Springer-Verlag. P. 61 . ISBN 3-540-54894-7 .
•    Niederreiter, Harald ; Xing, Chaoping (2001). „6. Zastosowania do algebraicznej teorii kodowania”. Wymierne punkty na krzywych nad ciałami skończonymi. Teoria i zastosowania . Seria notatek z wykładów London Mathematical Society. Tom. 285. Cambridge : Cambridge University Press . ISBN 0-521-66543-4 . Zbl 0971.11033 .