Aufgaben:Exercise 1.13Z: Binary Erasure Channel Decoding again: Difference between revisions
From LNTwww
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{quiz-Header|Buchseite= | {{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Linear_Block_Codes}} | ||
[[File:P_ID2541__KC_Z_1_13.png|right|frame| | [[File:P_ID2541__KC_Z_1_13.png|right|frame|Code table of the $\rm HC (7, 4, 3)$]] | ||
We consider again as in the [[Aufgaben:Exercise_1.13:_Binary_Erasure_Channel_Decoding|Task 1. 13]] the decoding of a [[Channel_Coding/Examples_of_Binary_Block_Codes#Hamming_Codes|Hamming Codes]] after transmission over an erasure channel ⇒ [[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Erasure_Channel_. E2.80.93_BEC|Binary Erasure Channel]] (abbreviated BEC). | |||
The $(7, 4, 3)$-Hamming code is fully described by the adjacent code table $\underline{u}_{i} → \underline{x}_{i}$ which can be used to find all solutions. | |||
| Line 13: | Line 13: | ||
Hints: | |||
* | * This exercise belongs to the chapter [[Channel_Coding/Decodierung_linearer_Blockcodes|Decoding of Linear Block Codes]]. | ||
* | * In contrast to [[Aufgaben:Exercise_1.13:_Binary_Erasure_Channel_Decoding|Exercise 1.13]] here the solution is not to be found formally, but intuitively. | ||
=== | ===Questions=== | ||
<quiz display=simple> | <quiz display=simple> | ||
What is the minimum distance $\ d_{\rm min}$ of the present code? | |||
|type="{}"} | |type="{}"} | ||
$\ d_{\rm min} \ = \ $ { 3 } | $\ d_{\rm min} \ = \ $ { 3 } | ||
{ | {Is the code systematic? | ||
|type="()"} | |type="()"} | ||
+ | + YES. | ||
- | - NO. | ||
{ | {Up to how many erasures (maximum number: $e_{\rm max})$ is successful decoding guaranteed? | ||
|type="{}"} | |type="{}"} | ||
$\ e_{\rm max} \ = \ $ { 2 } | $\ e_{\rm max} \ = \ $ { 2 } | ||
{ | {What is the sent information word $\underline{u}$ for $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$? | ||
|type="()"} | |type="()"} | ||
- $\underline{u} = (1, 0, 0, 0),$ | - $\underline{u} = (1, 0, 0, 0),$ | ||
| Line 41: | Line 41: | ||
- $\underline{u} = (1, 0, 1, 1).$ | - $\underline{u} = (1, 0, 1, 1).$ | ||
{ | {Which of the following received words can be decoded? | ||
|type="[]"} | |type="[]"} | ||
+ $\underline{y}_{\rm A }= (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E}),$ | + $\underline{y}_{\rm A }= (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E}),$ | ||
| Line 50: | Line 50: | ||
</quiz> | </quiz> | ||
=== | ===Solution=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
'''(1)''' | '''(1)''' The $(7, 4, 3)$ Hamming code is considered here. Accordingly, the minimum distance is $d_{\rm min} \ \underline{= 3}$. | ||
'''(2)''' | '''(2)''' The first $k = 4$ bits of each codeword $\underline{x}$ match the information word $\underline{u}$. Correct is therefore <u>YES</u>. | ||
'''(3)''' | '''(3)''' If no more than $e_{\rm max} = d_{\rm min} - 1 \underline{ = 2}$ bits are erased,decoding is possible with certainty. | ||
* | *Each codeword differs from every other in at least three bit positions. | ||
* | *With only two erasures, therefore, the codeword can be reconstructed in any case. | ||
'''(4)''' In | '''(4)''' In the code table, one finds a single codeword starting with "$10$" and ending with "$010$", namely $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$. | ||
Since this is a systematic code, the first $k = 4$ bits describe the information word $\underline{u} = (1, 0, 0, 1)$ ⇒ <u>answer 2</u>. | |||
'''(5)''' | '''(5)''' Correct are the <u>suggested solutions 1 and 2</u>. | ||
* $\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0)$ | * $\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0)$ cannot be decoded because less than $k = 4$ bits (number of information bits) arrive. | ||
* | *Also $\underline{y}_{\rm C} = ( {\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0)$ is not decodable because $\underline{x} = (0, 1, 1, 1, 0, 1, 0)$ and $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$ are possible outcomes. | ||
*$\underline{y}_{\rm B} = ( {\rm E}, {\rm E}, 0, {\rm E}, 0, 1, 0)$ | *$\underline{y}_{\rm B} = ( {\rm E}, {\rm E}, 0, {\rm E}, 0, 1, 0)$ is decodable, since of the 16 possible codewords only $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$ matches $\underline{y}_{\rm B}$ in positions 3, 5, 6, 7. | ||
*$\underline{y}_{\rm A} = (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E})$ | *$\underline{y}_{\rm A} = (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E})$ is decodable. Only the $m = 3$ parity bits are missing. Thus, the information word $\underline{u} = (1, 0, 0, 1)$ is also fixed (systematic code). | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Revision as of 23:59, 16 July 2022
We consider again as in the Task 1. 13 the decoding of a Hamming Codes after transmission over an erasure channel ⇒ Binary Erasure Channel (abbreviated BEC).
The $(7, 4, 3)$-Hamming code is fully described by the adjacent code table $\underline{u}_{i} → \underline{x}_{i}$ which can be used to find all solutions.
Hints:
- This exercise belongs to the chapter Decoding of Linear Block Codes.
- In contrast to Exercise 1.13 here the solution is not to be found formally, but intuitively.
Questions
Solution
(1) The $(7, 4, 3)$ Hamming code is considered here. Accordingly, the minimum distance is $d_{\rm min} \ \underline{= 3}$.
(2) The first $k = 4$ bits of each codeword $\underline{x}$ match the information word $\underline{u}$. Correct is therefore YES.
(3) If no more than $e_{\rm max} = d_{\rm min} - 1 \underline{ = 2}$ bits are erased,decoding is possible with certainty.
- Each codeword differs from every other in at least three bit positions.
- With only two erasures, therefore, the codeword can be reconstructed in any case.
(4) In the code table, one finds a single codeword starting with "$10$" and ending with "$010$", namely $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$.
Since this is a systematic code, the first $k = 4$ bits describe the information word $\underline{u} = (1, 0, 0, 1)$ ⇒ answer 2.
(5) Correct are the suggested solutions 1 and 2.
- $\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0)$ cannot be decoded because less than $k = 4$ bits (number of information bits) arrive.
- Also $\underline{y}_{\rm C} = ( {\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0)$ is not decodable because $\underline{x} = (0, 1, 1, 1, 0, 1, 0)$ and $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$ are possible outcomes.
- $\underline{y}_{\rm B} = ( {\rm E}, {\rm E}, 0, {\rm E}, 0, 1, 0)$ is decodable, since of the 16 possible codewords only $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$ matches $\underline{y}_{\rm B}$ in positions 3, 5, 6, 7.
- $\underline{y}_{\rm A} = (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E})$ is decodable. Only the $m = 3$ parity bits are missing. Thus, the information word $\underline{u} = (1, 0, 0, 1)$ is also fixed (systematic code).
