Difference between revisions of "Aufgaben:Exercise 1.13Z: Binary Erasure Channel Decoding again"
From LNTwww
| (18 intermediate revisions by 5 users not shown) | |||
| 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 as in the [[Aufgaben:Exercise_1.13:_Binary_Erasure_Channel_Decoding|"Exercise 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"]] $\rm (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 [[Channel_Coding/Decodierung_linearer_Blockcodes|"Decoding of Linear Block Codes"]]. | ||
| + | * In contrast to [[Aufgaben:Exercise_1.13:_Binary_Erasure_Channel_Decoding|"Exercise 1.13"]] the solution is here 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_{\ max} \ = \ $ { 2 | + | $\ e_{\rm max} \ = \ $ { 2 } |
| − | { | + | {The received word is $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$. What is the sent information word $\underline{u}$? |
| − | |type=" | + | |type="()"} |
- $\underline{u} = (1, 0, 0, 0),$ | - $\underline{u} = (1, 0, 0, 0),$ | ||
| − | + $\underline{u}= (1, 0, 0, 1),$ | + | + $\underline{u} = (1, 0, 0, 1),$ |
- $\underline{u} = (1, 0, 1, 0),$ | - $\underline{u} = (1, 0, 1, 0),$ | ||
- $\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 47: | Line 48: | ||
</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)''' The first $k = 4$ bits of each code word $\underline{x}$ match the information word $\underline{u}$. Correct is therefore <u>YES</u>. | ||
| + | |||
| + | |||
| + | '''(3)''' If no more than $e_{\rm max} = d_{\rm min}- 1 \ \ \underline{ = 2}$ bits are erased, decoding is possible with certainty. | ||
| + | *Each code word differs from every other in at least three bit positions. | ||
| + | |||
| + | *With only two erasures, therefore, the code word can be reconstructed in any case. | ||
| − | |||
| − | '''( | + | '''(4)''' In the code table, one finds a single code word 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. |
| − | *$\underline{y}_{\rm C} = ( {\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0)$ | + | *$\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 code words 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ß}} | ||
| − | [[Category: | + | [[Category:Channel Coding: Exercises|^1.5 Linear Block Code Decoding |
^]] | ^]] | ||
Latest revision as of 18:00, 1 November 2022
Code table of the $\rm HC (7, 4, 3)$
We consider as in the "Exercise 1. 13" the decoding of a "Hamming Codes" after transmission over an erasure channel ⇒ "Binary Erasure Channel" $\rm (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" the solution is here 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 code word $\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 code word differs from every other in at least three bit positions.
- With only two erasures, therefore, the code word can be reconstructed in any case.
(4) In the code table, one finds a single code word 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.
- $\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 code words 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).
