Volgende: Hoofdstuk 7: Convolutiecodes Omhoog: overview Vorige: Hoofdstuk 5: Principes van

Subsecties

• Aanvulling: grenzen voor minimale Hamming afstand voor blokcodes
  • Optimale waarden voor de minimale afstand
  • Bovengrenzen voor de minimale afstand
  • Asymptotische grenzen

Hoofdstuk 6: Cyclische blokcodes

27+2 pp.

Verduidelijking bij blz. 143-144:
in het algemeen is $G$ een $k \times n$ matrix, de data vector $d$ is een $1 \times k$ vector en de codewoord vector $c$ is een $1 \times n$ vector.

Verduidelijking bij figuur 6.2 en 6.3 op blz. 149-150 (de uitleg hierbij is nogal verwarrend):
de schakelingen van figuur 6.2 zijn beide schakelingen voor een vermenigvuldiging met $g(x)$. Figuur 6.3 a) is een schakeling voor een deling $\bmod g(x)$, waarbij het quotiënt onderaan bit per bit uitgelezen kan worden en de rest op het einde van de operatie in het register staat. Figuur 6.3 b) is opnieuw een vermenigvulding, ditmaal van $q(x)$ met $g(x)$ die het principe van figuur 6.3 a) illustreert. Merk op dat de schakelingen voor vermenigvuldigen en delen maar weinig verschillen. Voor meer details, zie blz.  van dit document.

Correctie op blz. 150, regel -9:
$H$ is een $(n-k)\times n$ matrix.

Opmerking op blz. 148:
let steeds goed op wat de afspraak is voor het afbeelden van een string op veeltermen:

• Laat men de meest linkse (dan wel meest rechtse) bit overeenkomen met de constante coëfficiënt?
• Wordt de hoogste of de laagste macht van $x$ eerst binnengeschoven in het register?

Deze afspraken kunnen nogal eens verschillen wat aanleiding geeft tot verwarring.

Opmerking op blz. 150:
verwar de `parity check matrix' (pariteitscheckmatrix) $H$ niet met de `parity matrix' (pariteitsmatrix) $P$ op blz. 144 (er bestaat trouwens geen consistente benaming voor de matrix $P$ in de literatuur).

Aanvulling op blz. 152:
men kan ook een pariteitscheckveelterm $h(x)$ definiëren als $h(x) = (x^n-1)/g(x)$. Er geldt dan dat:

$$h(x) \cdot c(x) \equiv 0 \bmod (x^n-1) .$$

Dit geeft een tweede methode om na te gaan of een veelterm van graad $n-1$ een codewoord is; de andere is kijken of $c(x) \bmod g(x) =0$. Naargelang de graad van $g(x)$ is één van beide methodes meer efficiënt.

Correctie op blz. 160, regel -3:
burst of errors.

Correctie op blz. 162:
laatste lijn van de grote matrix:

$$[ 0 0 0 1 0 0 0 1]$$

Correctie op blz. 173, Figure 6.12:
(d) $n = 511$

Hoofdstuk 6.4.3 valt weg (blz. 166-170).

Aanvulling: grenzen voor minimale Hamming afstand voor blokcodes

Optimale waarden voor de minimale afstand

Tabel 1 geeft voor kleine waarden van $n$ en $k$ ($n \leq 16$) aan wat de optimale minimale afstand $\mbox{$d_{\mbox{\footnotesize min}}$}$ is van de beste lineaire binaire codes. Er bestaan grotere on-line tabellen, ook voor niet-binaire codes: http://www.win.tue.nl/~aeb/voorlincod.html

Tabel: Maximale waarde van $\mbox{$d_{\mbox{\footnotesize min}}$}$ voor $(n,k)$ lineaire binaire codes

	dimensie $k$
lengte	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$n$
2	1
3	2	1
4	2	2	1
5	3	2	2	1
6	4	3	2	2	1
7	4	4	3	2	2	1
8	5	4	4	2	2	2	1
9	6	4	4	3	2	2	2	1
10	6	5	4	4	3	2	2	2	1
11	7	6	5	4	4	3	2	2	2	1
12	8	6	6	4	4	4	3	2	2	2	1
13	8	7	6	5	4	4	4	3	2	2	2	1
14	9	8	7	6	5	4	4	4	3	2	2	2	1
15	10	8	8	7	6	5	4	4	4	3	2	2	2	1
16	10	8	8	8	6	6	5	4	4	4	2	2	2	2	1

Bovengrenzen voor de minimale afstand

• Hamming: binair: $2^{n-k} \ge \sum\limits^{t}_{j=0} C_j^n$
  
  

  Het bewijs hiervan volgt door het volume te berekenen van een bol met straal $t$ rond elk van de $q^k$ codewoorden in de $n$-dimensionale ruimte. Het volume van zo een bol is $\sum_limits^{t}_{j=0} C_j^n$. De grens volgt dan uit de beschouwing dat het totaal volume van al die bollen kleiner moet zijn dan het totale volume van de ruimte, $q^n$.

  Codes die voldoen aan de Hamminggrens worden perfecte codes genoemd. Er zijn slechts drie perfecte codes:

  • de $(n,1)$ herhalingscode voor $n$ oneven;
  • de Hammingcodes (ook de niet-binaire);
  • de $(23,12)$ binaire Golay code en de (11,6) ternaire ($q=3$) Golay code.
  In 1974 heeft de Fin Tietavainen aangetoond dat er geen andere perfecte codes bestaan.

• Singleton grens:
  
  

  Dit kan men eenvoudig bewijzen door een rij te beschouwen van een generatormatrix $G$ in systematische vorm. De eerste $k$ kolommen bevatten slechts 1 niet-nul element, de volgende $n-k$ kolommen kunnen ten hoogste $n-k$ niet-nul elementen bevatten, dus de minimale afstand van een lineaire code kan ten hoogste $n-k+1$ zijn.

  Een belangrijk gevolg van de Singleton grens is dat voor lange codes minstens twee bijkomende symbolen nodig zijn om 1 bijkomende fout te kunnen verbeteren. Of, een code met $R=k/n=1/2$ kan voor grote $n$ ten hoogste $25\%$ fouten in een codewoord verbeteren. Codes die voldoen aan de Singletongrens worden Maximale Afstand Scheidbare (MDS, Maximal Distance Separable) codes genaamd.

  De enige binaire MDS codes zijn de $(n,1)$ herhalingscodes en de $(n,n-1)$ pariteitscodes. Reed-Solomon codes zijn de belangrijkste niet-binaire MDS codes.

• Plotkin grens: binair: $d_{min} \le \frac{n 2^{k-1}}{2^k - 1}$

Asymptotische grenzen

Men kan ook asymptotische onder- en bovengrenzen berekenen voor de rate $R$ in functie van de fractionele minimale afstand $\mbox{$d_{\mbox{\footnotesize min}}$}$$/n$ (zie Figuur 1); hier betekent asymptotisch voor $n \longrightarrow \infty$. De Gilbert grens is een ondergrens; alle andere grenzen zijn bovengrenzen. De gedetailleerde afleiding van deze resultaten valt buiten de leerstof, maar je moet wel deze grafiek correct kunnen interpreteren. We weten dus dat er asymptotisch gezien goede codes bestaan, maar er zijn geen goede constructies bekend. Er zijn wel codes die voor `kleine' waarden van $n$ (tot 100-150) de grenzen dicht benaderen. Men vermoedt dat ook voor grotere waarden van $n$ codes bestaan in het grijze gebied, maar de constructie daarvan is nog altijd een open probleem.

Figuur: Asymptotische onder- en bovengrenzen voor $R$ in functie van $d_{min}/n$

Volgende: Hoofdstuk 7: Convolutiecodes Omhoog: overview Vorige: Hoofdstuk 5: Principes van