Difference between revisions of "Aufgaben:Exercise 1.5Z: SPC (5, 4) vs. RC (5, 1)"
(18 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | {{quiz-Header|Buchseite= | + | {{quiz-Header|Buchseite=Channel_Coding/Examples_of_Binary_Block_Codes |
}} | }} | ||
− | [[File:P_ID2386__KC_Z_1_5.png|right|frame|Single | + | [[File:P_ID2386__KC_Z_1_5.png|right|frame|Single parity-check code and repetition code with $n = 5$]] |
− | + | There is a certain relationship between the "single parity-check code" and the "repetition code" of the same code length $n$. As will be shown in the chapter [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]] they are so called "dual codes". | |
− | |||
− | * | + | *The [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity_Check_Codes|single parity-check code]] with parameters $k = 4$ and $n = 5$ ⇒ $\rm SPC \ (5, 4)$ adds to the four information bits $u_{1}$, ... , $u_{4}$ a check bit $p$ so that an even number of ones occurs in each code word $\underline{x}$: |
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$ | :$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$ | ||
− | *Ein jeder [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscode]](englisch: ''Repetition Code'') ist durch den Codeparameter $k = 1$ charakterisiert. Beim RC (5, 1) lauten die beiden Codeworte (0, 0, 0, 0, 0) und (1, 1, 1, 1, 1). | + | '''deutscher Text:''' |
+ | *Ein jeder [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscode]] (englisch: ''Repetition Code'') ist durch den Codeparameter $k = 1$ charakterisiert. Beim $\rm RC \ (5, \ 1)$ lauten die beiden Codeworte $(0, 0, 0, 0, 0)$ und $(1, 1, 1, 1, 1)$. | ||
− | + | '''Deine Übersetzung:''' | |
+ | *Each [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|repetition code]] is characterized by the code parameter $k = 1$. For $\rm RC \ (5, \ 1)$ the two code words are $(0, 0, 0, 0)$ and $(1, 1, 1, 1)$. | ||
− | |||
− | |||
− | === | + | The graphic shows the basic structure of these two codes, which will be compared in this task. |
+ | |||
+ | |||
+ | |||
+ | |||
+ | Hints: | ||
+ | *This exercise belongs to the chapter [[Channel_Coding/Examples_of_Binary_Block_Codes|"Examples of Binary Block Codes"]]. | ||
+ | |||
+ | *Reference is made in particular to the pages [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes|"Single Parity-check Codes"]] and [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|"Repetition Codes"]]. | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===Questions=== | ||
<quiz display=simple> | <quiz display=simple> | ||
− | { | + | {How do the $\text{SPC (5, 4)}$ and the $\text{RC (5, 1)}$ differ in terms of code size? |
|type="{}"} | |type="{}"} | ||
− | $\ {\rm SPC} (5, 4): | + | $\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 16 3% } |
− | $\ {\rm | + | $\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \ = \ $ { 2 3% } |
− | { | + | {Which of the following code words are possible in the $\text{SPC (5, 4)}$ ? |
|type="[]"} | |type="[]"} | ||
− | + (0, 0, 0, 0, 0), | + | + $(0, 0, 0, 0, 0)$, |
− | - (0, 0, 1, 0, 0), | + | - $(0, 0, 1, 0, 0)$, |
− | + (1, 1, 0, 1, 1), | + | + $(1, 1, 0, 1, 1)$, |
− | - (1, 1, 1, 1, 1). | + | - $(1, 1, 1, 1, 1)$. |
− | { | + | {Which of the following code words are possible in the $\text{RC (5, 1)}$ ? |
|type="[]"} | |type="[]"} | ||
− | + (0, 0, 0, 0, 0), | + | + $(0, 0, 0, 0, 0)$, |
− | - (0, 0, 1, 0, 0), | + | - $(0, 0, 1, 0, 0)$, |
− | - (1, 1, 0, 1, 1), | + | - $(1, 1, 0, 1, 1)$, |
− | +(1, 1, 1, 1, 1). | + | +$(1, 1, 1, 1, 1)$. |
− | { | + | {How many code sequences $(N)$ must be included in the maximum likelihood decision? |
|type="{}"} | |type="{}"} | ||
− | $\ {\rm SPC} (5, 4): | + | $\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}N \ = \ $ { 32 } |
− | $ | + | $ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}N \ = \ $ { 32 } |
− | { | + | {What is the minimum distance between the two codes? |
|type="{}"} | |type="{}"} | ||
− | $\ {\rm SPC} (5, 4): | + | $\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $ { 2 } |
− | $\ {\rm RC} (5, 1): | + | $\ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}d_{\rm min} \ = \ $ { 5 } |
− | { | + | {Up to how many bit errors $(e)$ does error detection work? |
|type="{}"} | |type="{}"} | ||
− | $\ {\rm SPC} (5, 4): | + | $\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}e \ = \ $ { 1 } |
− | $ | + | $ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}e \ = \ $ { 4 } |
− | { | + | {Up to how many bit errors $(t)$ does error correction work? |
|type="{}"} | |type="{}"} | ||
− | $\ {\rm SPC} (5, 4): | + | $\ {\rm SPC} \ (5, 4)\text{:}\hspace{0.4cm}t \ = \ $ { 0. } |
− | $ | + | $ {\rm RC} \ (5, 1)\text{:}\hspace{0.6cm}t \ = \ $ { 2 } |
</quiz> | </quiz> | ||
− | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' | + | '''(1)''' The code size gives the number of possible code words. It holds $|\mathcal{C}| = 2^k$, so that there are |
+ | *in the single parity-check code considered here, there are <u>16 code words</u> ($k = 4$), and | ||
+ | *in the repetition code, only <u>two code words</u> ($k = 1$). | ||
+ | |||
+ | |||
+ | '''(2)''' For any single parity-check code, the number of ones is even ⇒ <u>answers 1 and 3</u>. | ||
+ | |||
+ | |||
+ | '''(3)''' For any repetition code, there are only two code words (independent of $n$), both given here ⇒ <u>Answer 1 and 4</u>. | ||
+ | |||
+ | |||
+ | '''(4)''' Due to bit errors, there can always be $N = 2^n \hspace{0.15cm}\underline{= 32}$ different bit combinations for the receive vector $\underline{y}$. | ||
+ | *All of which must be included in the maximum likelihood decision. | ||
+ | *This is true for both the $\text{SPC (5, 4)}$ and the $\text{RC (5, 1)}$. | ||
+ | |||
+ | |||
− | '''( | + | '''(5)''' For the $\text{SPC (5, 4)}$, the Hamming distance between any two code words is at least $d_{\rm min} \hspace{0.15cm}\underline{= 2}$. In contrast, for $\text{RC (5, 1)}$, all bits of the two code words are different ⇒ $d_{\rm min} \hspace{0.15cm}\underline{= 5}$. |
− | |||
− | |||
+ | '''(6)''' Error detection is possible as long as there are no more than $e = d_{\rm min} - 1$ bit errors in a code word. | ||
+ | *Using the result from '''(5)''', we obtain $\underline{e = 1}$ (SPC) or $\underline{e = 4}$ (RC). | ||
− | |||
− | |||
− | '''(7)''' | + | '''(7)''' In general, for the number of correctable errors: |
:$$t = \left\lfloor \frac{d_{\rm min}-1}{2} \right\rfloor \hspace{0.05cm}.$$ | :$$t = \left\lfloor \frac{d_{\rm min}-1}{2} \right\rfloor \hspace{0.05cm}.$$ | ||
− | + | *For any single parity check code, $(d_{\rm min} - 1)/2 = 0.5$ ⇒ $\underline{t = 0}$. | |
+ | *In contrast, $\text{RC (5, 1)}$ can be used to correct errors up to $\underline{t = 2}$ because of $d_{\rm min} = 5$. | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Line 89: | Line 115: | ||
− | [[Category: | + | [[Category:Channel Coding: Exercises|^1.3 Examples of Binary Block Codes^]] |
− | ^]] |
Latest revision as of 18:55, 1 November 2022
There is a certain relationship between the "single parity-check code" and the "repetition code" of the same code length $n$. As will be shown in the chapter "General Description of Linear Block Codes" they are so called "dual codes".
- The single parity-check code with parameters $k = 4$ and $n = 5$ ⇒ $\rm SPC \ (5, 4)$ adds to the four information bits $u_{1}$, ... , $u_{4}$ a check bit $p$ so that an even number of ones occurs in each code word $\underline{x}$:
- $$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} u_1 \oplus u_2 \oplus u_3 \oplus u_4 \oplus p = 0 \hspace{0.05cm}.$$
deutscher Text:
- Ein jeder Wiederholungscode (englisch: Repetition Code) ist durch den Codeparameter $k = 1$ charakterisiert. Beim $\rm RC \ (5, \ 1)$ lauten die beiden Codeworte $(0, 0, 0, 0, 0)$ und $(1, 1, 1, 1, 1)$.
Deine Übersetzung:
- Each repetition code is characterized by the code parameter $k = 1$. For $\rm RC \ (5, \ 1)$ the two code words are $(0, 0, 0, 0)$ and $(1, 1, 1, 1)$.
The graphic shows the basic structure of these two codes, which will be compared in this task.
Hints:
- This exercise belongs to the chapter "Examples of Binary Block Codes".
- Reference is made in particular to the pages "Single Parity-check Codes" and "Repetition Codes".
Questions
Solution
- in the single parity-check code considered here, there are 16 code words ($k = 4$), and
- in the repetition code, only two code words ($k = 1$).
(2) For any single parity-check code, the number of ones is even ⇒ answers 1 and 3.
(3) For any repetition code, there are only two code words (independent of $n$), both given here ⇒ Answer 1 and 4.
(4) Due to bit errors, there can always be $N = 2^n \hspace{0.15cm}\underline{= 32}$ different bit combinations for the receive vector $\underline{y}$.
- All of which must be included in the maximum likelihood decision.
- This is true for both the $\text{SPC (5, 4)}$ and the $\text{RC (5, 1)}$.
(5) For the $\text{SPC (5, 4)}$, the Hamming distance between any two code words is at least $d_{\rm min} \hspace{0.15cm}\underline{= 2}$. In contrast, for $\text{RC (5, 1)}$, all bits of the two code words are different ⇒ $d_{\rm min} \hspace{0.15cm}\underline{= 5}$.
(6) Error detection is possible as long as there are no more than $e = d_{\rm min} - 1$ bit errors in a code word.
- Using the result from (5), we obtain $\underline{e = 1}$ (SPC) or $\underline{e = 4}$ (RC).
(7) In general, for the number of correctable errors:
- $$t = \left\lfloor \frac{d_{\rm min}-1}{2} \right\rfloor \hspace{0.05cm}.$$
- For any single parity check code, $(d_{\rm min} - 1)/2 = 0.5$ ⇒ $\underline{t = 0}$.
- In contrast, $\text{RC (5, 1)}$ can be used to correct errors up to $\underline{t = 2}$ because of $d_{\rm min} = 5$.