Difference between revisions of "Aufgaben:Exercise 1.13Z: Binary Erasure Channel Decoding again"
From LNTwww
| 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
Code table of the $\rm HC (7, 4, 3)$
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).
