Exercise 1.11: Syndrome Decoding

[[File:EN_KC_A_1_11.png|right|frame|Syndrome and coset leaders
$($incomplete list$) of $\rm HC \ (7, \, 4, \, 3)$ ]] To decode a $(7, \, 4, \, 3)$ Hamming code, which is defined by its parity-check matrix :'"`UNIQ-MathJax27-QINU`"' "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)$: :'"`UNIQ-MathJax28-QINU`"' *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 codeword}) + \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} =

\underline{0}$:
:'"`UNIQ-MathJax29-QINU`"'

*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)$


are to be determined in the subtasks  '''(4)'''  and  '''(5)'''.






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:
:'"`UNIQ-MathJax30-QINU`"'
*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$.
 




==='"`UNIQ--h-0--QINU`"'Questions===
'"`UNIQ--quiz-00000002-QINU`"'

==='"`UNIQ--h-1--QINU`"'Solution===
'"`UNIQ--html-00000003-QINU`"'
'''(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,  

:'"`UNIQ-MathJax31-QINU`"'

:and just as many  "cosets".  

*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:

:'"`UNIQ-MathJax32-QINU`"'

*The cosets  ${\it \Psi}_{0}$  include for example - see sample solution to  [[Aufgaben:Exercise_1.11Z:_Syndrome_Decoding_again|"Exercise 1.11Z"]] - the vectors

:'"`UNIQ-MathJax33-QINU`"'
:'"`UNIQ-MathJax34-QINU`"'



'''(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}$:
:'"`UNIQ-MathJax35-QINU`"'

 

 [[File:P_ID2398__KC_A_1_11d.png|right|frame|All coset leaders of the  $(7, \, 4, \, 3)$  Hamming code '''Korrektur''' ]] 
'''(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:

:'"`UNIQ-MathJax36-QINU`"'

:'"`UNIQ-MathJax37-QINU`"'

:'"`UNIQ-MathJax38-QINU`"'

:'"`UNIQ-MathJax39-QINU`"'

:'"`UNIQ-MathJax40-QINU`"'

:'"`UNIQ-MathJax41-QINU`"'

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 corrupted during transmission.  It follows:

:'"`UNIQ-MathJax42-QINU`"'

*Uncoded transmission of a block with  $n = k = 4$  bits would result in the same BSC channel:

:'"`UNIQ-MathJax43-QINU`"'

*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$)$.