Zur Decodierung eines (7, 4, 3)–Hamming–Codes, der durch seine Prüfmatrix
"syndrome decoding" is also suitable. Since all Hamming codes are perfect, the result is as good as with the $($in the general case$)$ more complicated maximum likelihood decoding.
For [[Channel_Coding/Decoding_of_Linear_Block_Codes#Principle_of_syndrome_decoding|"syndrome decoding"]] one proceeds as follows:
*From the received vector $\underline{y}$ one forms the syndrome $($it holds $m = n - k)$:
*In [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|"BSC channel"]] the received word $\underline{y} = \underline{x} \, ({\rm code\:word}) + \underline{e} \, ({\rm error\:vector})$ is also an element of ${\rm GF}(2^n)$, and it holds because of $ \underline{x} · \boldsymbol {{\rm H} }^{\rm T} =
*Many error patterns $\underline{e}$ lead to the same syndrome $\underline{s}$. One now groups those error patterns with the same syndrome $\underline{s}_{\mu}$ to the coset ${\it \Psi}_{\mu}$.
*The coset leader $\underline{e}_{\mu}$ is the fault vector that has the lowest Hamming weight within the class ${\it \Psi}_{\mu}$ and is accordingly the most probable. If there are several of these, one chooses one of them arbitrarily.
gegeben ist, eignet sich auch die ''Syndromdecodierung''. Da alle Hamming–Codes perfekt sind, ergibt sich hiermit ein gleich gutes Ergebnis wie mit der (im allgemeinen Fall) komplizierteren Maximum–Likelihood–Detektion.
The above graph shows the incomplete list of coset leaders $\underline{e}_{\mu}$ for each $\underline{s}_{\mu}$.
The most likely error vectors
*$\underline{e}_{3}$ with syndrome $\underline{s}_{3} = (0, 1, 1)$,
*$\underline{e}_{5}$ with syndrome $\underline{s}_{5} = (1, 0, 1)$,
*$\underline{e}_{6}$ with syndrome $\underline{s}_{6} = (1, 1, 0)$,
*$\underline{e}_{7}$ with syndrome $\underline{s}_{7} = (1, 1, 1)$
Bei der [[Kanalcodierung/Decodierung_linearer_Blockcodes#Prinzip_der_Syndromdecodierung|Syndromdecodierung]] geht man wie folgt vor:
*Man bildet aus dem Empfangsvektor <u>y</u> das Syndrom (es gilt $m = n – k$):
*Beim [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC–Kanal]] ist auch das Empfangswort $y = x$ (Codewort) + <u>''e''</u> (Fehlervektor) ein Element von GF ($2^n$), und es gilt wegen $ \underline{x} · \boldsymbol {{\rm H} }^{\rm T} =
are to be determined in the subtasks '''(4)''' and '''(5)'''.
*Viele Fehlermuster <u>''e''</u> führen zum gleichen Syndrom <u>''s''</u>. Man fasst nun diejenigen Fehlermuster mit dem gleichen Syndrom $s_{\mu}$ zur Nebenklasse $\Psi_{\mu}$ zusammen.
*Als Nebenklassenanführer $\underline{e}_{\mu}$ bezeichnet man denjenigen Fehlervektor, der innerhalb der Klasse $\Psi_{\mu}$ das geringste Hamming–Gewicht aufweist und dementsprechend am wahrscheinlichsten ist.
Die obige Grafik zeigt die unvollständige Liste der Nebenklassenanführer $\underline{e}_{\mu}$ für die einzelnen $s_{\mu}$ .
Die wahrscheinlichsten Fehlervektoren
*$\underline{e}_{3}$ mit Syndrom $\underline{s}_{3} = (0, 1, 1)$,
*$\underline{e}_{5}$ mit Syndrom $\underline{s}_{5} = (1, 0, 1)$,
*$\underline{e}_{6}$ mit Syndrom $\underline{s}_{6} = (1, 1, 0)$,
*$\underline{e}_{7}$ mit Syndrom $\underline{s}_{7} = (1, 1, 1)$
sollen in den Teilaufgaben (4) und (5) ermittelt werden.
''Hinweis:''
Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes|Decodierung linearer Blockcodes]]. Zugrunde liegt ein Hamming–Code mit den Parametern $n = 7$ und $k = 4 ⇒ m = 3$. Alle Codeworte haben folgendes Format:
Hints:
* This exercise belongs to the chapter [[Channel_Coding/Decoding_of_Linear_Block_Codes|"Decoding of Linear Block Codes"]].
* Underlying is a Hamming code with parameters $n = 7$, $k = 4$ ⇒ $m = 3$. All code words have the following format:
*The parity-check equations are illustrated on the information sheet for [[Aufgaben:Exercise_1.11Z:_Syndrome_Decoding_again|"Exercise 1.11Z"]] which considers the same constellation as in the present exercise.
*In the last subtask '''(6)''', use the BSC parameter $ \varepsilon = 0.1$.
Die Prüfgleichungen sind auf dem Angabenblatt zur [[Aufgaben:1.11Z_Nochmals_Syndromdecodierung|Aufgabe 1.11Z]] veranschaulicht, in der genau die gleiche Konstellation betrachtet wird wie in der vorliegenden Aufgabe. Verwenden Sie in der letzten Teilaufgabe (6) den BSC–Parameter $ \epsilon = 0.1$.
===Fragebogen===
===Questions===
<quiz display=simple>
<quiz display=simple>
{Multiple-Choice Frage
{How many received words $(N_{0})$ lead to the syndrome $\underline{s} = \underline{s}_{0} = (0, 0, 0)$?
|type="{}"}
$N_{0} \ = \ $ { 16 3% }
{How many received words $(N_{7})$ lead to the syndrome $\underline{s} = \underline{s}_{7} = (1, 1, 1)$?
|type="{}"}
$N_{7} \ = \ $ { 16 3% }
{What are the characteristics of all coset leaders $\underline{e}_{\mu}$?
|type="[]"}
|type="[]"}
- Falsch
- The last three bits of $\underline{e}_{\mu}$ are identical to $\underline{s}_{\mu}$ .
+ Richtig
- All $\underline{e}_{\mu}$ contain a single "$1$" each.
+ All $\underline{e}_{\mu}$ include at most one "$1$".
{What syndrome $\underline{s}_{\mu}$ does the error vector $(1, 0, 0, 0, 0, 0, 0)$ lead to?
{What is the block error probability for the BSC model with falsification probability $\varepsilon = 0.1$?
|type="{}"}
${\rm Pr(block\:error)} \ = \ $ { 15 3% } $\ \%$
</quiz>
</quiz>
===Musterlösung===
===Solution===
{{ML-Kopf}}
{{ML-Kopf}}
'''1.'''
'''(1)''' There are a total of $2^7 = 128$ different code words $\underline{x}$ and according to the BSC model also $2^7$ different received words $y$ and as many error vectors $\underline{e}$.
'''2.'''
'''3.'''
*With $m = 3$ parity bits, there are $2^3 = 8$ distinct values for the syndrome,
*Since in the Hamming code, which is perfect, all error vectors belong to one of the eight cosets ${\it \Psi}_{\mu}$ and, moreover, the number of all vectors in all cosets is the same ("Why should it be different?" Is that enough proof for you?), we get:
*The cosets ${\it \Psi}_{0}$ include for example - see sample solution to [[Aufgaben:Exercise_1.11Z:_Syndrome_Decoding_again|"Exercise 1.11Z"]] - the vectors
:$$\underline{e} = (1, 1, 0, 0, 0, 0, 1),$$
:$$\underline{e} = (1, 1, 1, 1, 1, 1, 1).$$
'''(2)''' According to the comments of the last partial result, the following applies equally: $N_{7} \ \underline{= 16}$.
'''(3)''' Correct is <u>answer 3</u>:
*The coset leader $\underline{e}_{\mu}$ is the error vector $\underline{e}$ with the lowest [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"Hamming weight"]] $w_{\rm H}(\underline{e})$ that leads to the syndrome $\underline{s}_{\mu}$.
*The (7, 4, 3) Hamming code considered here is perfect. That is, all eight coset leaders therefore contain.
:*either no "one" $(\underline{e}_{0}$ ⇒ no correction is required$)$, or
:*exactly a single "one" $(\underline{e}_{1}, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \underline{e}_{7}$ ⇒ an information or parity bit must be corrected$)$.
'''(4)''' It holds $\underline{s} = \underline{e} · \boldsymbol{\rm H}^{\rm T}$:
[[File:EN_KC_A_1_11d_v2.png|right|frame|All coset leaders of the $\rm HC (7, \, 4, \, 3)$ ]]
'''(5)''' A comparison with the solution to the last subtask shows that $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$ as a syndrome gives the second row of the transposed matrix:
The adjacent graph summarizes again the results of the subtasks '''(4)''' and '''(5)'''.
'''(6)''' For the $(7, \, 4, \, 3)$ Hamming code under consideration, the correct information word is decided if at most one bit within the code word is falsified during transmission. It follows:
*The comparison is not entirely fair, however, since with $n = 4$ a smaller falsification probability $\varepsilon$ would have to be applied than with $n = 7$ $($smaller symbol rate ⇒ smaller bandwidth ⇒ smaller noise power$)$.
{{ML-Fuß}}
[[Category:Aufgaben zu Kanalcodierung|^1.5 Decodierung linearer Blockcodes
^]]
[[Category:Channel Coding: Exercises|^1.5 Linear Block Code Decoding^]]
"syndrome decoding" is also suitable. Since all Hamming codes are perfect, the result is as good as with the $($in the general case$)$ more complicated maximum likelihood decoding.
In "BSC channel" the received word $\underline{y} = \underline{x} \, ({\rm code\:word}) + \underline{e} \, ({\rm error\:vector})$ is also an element of ${\rm GF}(2^n)$, and it holds because of $ \underline{x} · \boldsymbol {{\rm H} }^{\rm T} =
Many error patterns $\underline{e}$ lead to the same syndrome $\underline{s}$. One now groups those error patterns with the same syndrome $\underline{s}_{\mu}$ to the coset ${\it \Psi}_{\mu}$.
The coset leader $\underline{e}_{\mu}$ is the fault vector that has the lowest Hamming weight within the class ${\it \Psi}_{\mu}$ and is accordingly the most probable. If there are several of these, one chooses one of them arbitrarily.
The above graph shows the incomplete list of coset leaders $\underline{e}_{\mu}$ for each $\underline{s}_{\mu}$.
The most likely error vectors
$\underline{e}_{3}$ with syndrome $\underline{s}_{3} = (0, 1, 1)$,
$\underline{e}_{5}$ with syndrome $\underline{s}_{5} = (1, 0, 1)$,
$\underline{e}_{6}$ with syndrome $\underline{s}_{6} = (1, 1, 0)$,
$\underline{e}_{7}$ with syndrome $\underline{s}_{7} = (1, 1, 1)$
The parity-check equations are illustrated on the information sheet for "Exercise 1.11Z" which considers the same constellation as in the present exercise.
In the last subtask (6), use the BSC parameter $ \varepsilon = 0.1$.
(1) There are a total of $2^7 = 128$ different code words $\underline{x}$ and according to the BSC model also $2^7$ different received words $y$ and as many error vectors $\underline{e}$.
With $m = 3$ parity bits, there are $2^3 = 8$ distinct values for the syndrome,
Since in the Hamming code, which is perfect, all error vectors belong to one of the eight cosets ${\it \Psi}_{\mu}$ and, moreover, the number of all vectors in all cosets is the same ("Why should it be different?" Is that enough proof for you?), we get:
The cosets ${\it \Psi}_{0}$ include for example - see sample solution to "Exercise 1.11Z" - the vectors
$$\underline{e} = (1, 1, 0, 0, 0, 0, 1),$$
$$\underline{e} = (1, 1, 1, 1, 1, 1, 1).$$
(2) According to the comments of the last partial result, the following applies equally: $N_{7} \ \underline{= 16}$.
(3) Correct is answer 3:
The coset leader $\underline{e}_{\mu}$ is the error vector $\underline{e}$ with the lowest "Hamming weight" $w_{\rm H}(\underline{e})$ that leads to the syndrome $\underline{s}_{\mu}$.
The (7, 4, 3) Hamming code considered here is perfect. That is, all eight coset leaders therefore contain.
either no "one" $(\underline{e}_{0}$ ⇒ no correction is required$)$, or
exactly a single "one" $(\underline{e}_{1}, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \underline{e}_{7}$ ⇒ an information or parity bit must be corrected$)$.
(4) It holds $\underline{s} = \underline{e} · \boldsymbol{\rm H}^{\rm T}$:
(5) A comparison with the solution to the last subtask shows that $(0, 1, 0, 0, 0, 0, 0) \cdot \boldsymbol{\rm H}^{\rm T}$ as a syndrome gives the second row of the transposed matrix:
The adjacent graph summarizes again the results of the subtasks (4) and (5).
(6) For the $(7, \, 4, \, 3)$ Hamming code under consideration, the correct information word is decided if at most one bit within the code word is falsified during transmission. It follows:
The comparison is not entirely fair, however, since with $n = 4$ a smaller falsification probability $\varepsilon$ would have to be applied than with $n = 7$ $($smaller symbol rate ⇒ smaller bandwidth ⇒ smaller noise power$)$.
