View source for Aufgaben:Exercise 3.1Z: Convolution Codes of Rate 1/2

{{quiz-Header|Buchseite=Channel_Coding/Basics_of_Convolutional_Coding}}

[[File:EN_KC_Z_3_1_jetztaber.png|right|frame|Convolutional codes of rate &nbsp;$1/2$]]
The graphic shows two convolutional encoders of rate&nbsp; $R = 1/2$:&nbsp; 
*At the input there is the information sequence&nbsp; $\underline {u} = (u_1, u_2, \ \text{...} \ , u_i, \ \text{...})$.&nbsp; 

*From this,&nbsp; modulo-2 operations generate the two sequences
:$$\underline{\it x}^{(1)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}   \big( \hspace{0.05cm}x_1^{(1)}\hspace{0.05cm},\hspace{0.05cm} x_2^{(1)}\hspace{0.05cm},\hspace{0.05cm} \text{...} \hspace{0.05cm},\hspace{0.05cm}  
 x_i^{(1)} \hspace{0.05cm},\text{...} \hspace{0.05cm} \big )\hspace{0.05cm},$$
:$$\underline{\it x}^{(2)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}   \big( \hspace{0.05cm}x_1^{(2)}\hspace{0.05cm},\hspace{0.05cm} x_2^{(2)}\hspace{0.05cm},\hspace{0.05cm}\text{...} \hspace{0.05cm},\hspace{0.05cm}  
 x_i^{(2)} \hspace{0.05cm}, \text{...} \hspace{0.05cm} \big )$$

:where&nbsp; $x_i^{(j)}$&nbsp; with&nbsp; $j = 1$&nbsp; resp.&nbsp; $j = 2$&nbsp;  may depend except from&nbsp; $u_i$&nbsp; also from the previous information bits&nbsp; $u_{i-1}, \ \text{...} \ , u_{i-m}$. 

*One refers&nbsp; $m$&nbsp; as the&nbsp; "memory"&nbsp; and&nbsp; $\nu = m + 1$&nbsp; as the&nbsp; "influence length"&nbsp; of the code&nbsp;  $($or of the encoder$)$.

* The considered encoders &nbsp;$\rm A$&nbsp; and &nbsp;$\rm B$&nbsp; differ with respect to these quantities.




<u>Hints:</u>
*The exercise refers to the chapter&nbsp; [[Channel_Coding/Basics_of_Convolutional_Coding| "Basics of Convolutional Coding"]].

*Not shown in the diagram is the multiplexing of the two subsequences&nbsp; $\underline {x}^{(1)}$&nbsp; and&nbsp; $\underline {x}^{(2)}$&nbsp; to the resulting code sequence&nbsp; 
:$$\underline {x} = (x_1^{(1)}, x_1^{(2)}, x_2^{(1)}, x_2^{(2)}, \ \text{...}).$$ 
*In subtasks&nbsp; '''(3)'''&nbsp; to&nbsp; '''(5)'''&nbsp; you are to determine the start of the sequences&nbsp; $\underline {x}^{(1)}, \underline{x}^{(2)}$&nbsp; and&nbsp; $\underline{x}$&nbsp; assuming the information sequence&nbsp; 
:$$\underline{u} = (1, 0, 1, 1, 0, 0, \ \text{. ..}).$$ 



===Questions===
<quiz display=simple>
{In which code parameters do encoder &nbsp;$\rm A$&nbsp; and encoder &nbsp;$\rm B$ differ?
|type="[]"}
- $k$: &nbsp; &nbsp; Number of information bits processed per coding step,
- $n$: &nbsp; &nbsp; Number of code bits output per coding step,
+ $m$: &nbsp; memory order of the code,
+ $\nu$: &nbsp; &nbsp; influence length of the code.

{Which encoder exhibits the memory&nbsp; $m = 2$?
|type="[]"}
- Encoder &nbsp;$\rm A$,
+ encoder &nbsp;$\rm B$.

{What is the partial code sequence&nbsp; $\underline {x}^{(1)}$&nbsp; of encoder &nbsp;$\rm B$&nbsp; for&nbsp; $\underline {u} = (1, 0, 1, 1, 0, 0, \ \text{...})$?
|type="()"}
+ $\underline {x}^{(1)} = (1, 1, 0, 0, 0, 1, 0, 0, \ ...)$,
- $\underline {x}^{(1)} = (1, 0, 1, 1, 0, 0, 0, 0, \ ...)$.

{What is the partial code sequence&nbsp; $\underline {x}^{(2)}$&nbsp; of encoder &nbsp;$\rm B$&nbsp; for&nbsp; $\underline {u} = (1, 0, 1, 1, 0, 0, \ \text{...})$
|type="()"}
- $\underline{x}^{(2)} = (1, 1, 0, 0, 0, 1, 0, 0, \ \text{...})$,
+ $\underline{x}^{(2)} = (1, 0, 0, 1, 1, 1, 0, 0, \ \text{...})$.

{How does the entire code sequence&nbsp; $\underline {x}$&nbsp; start from encoder &nbsp;$\rm B$&nbsp; after multiplexing?
|type="()"}
+ $\underline {x} = (1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, \ \text{...})$,
- $\underline {x} = (1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, \ \text{...})$.
</quiz>

===Solution===
{{ML-Kopf}}
'''(1)'''&nbsp; For both encoders,&nbsp; $k = 1$&nbsp; and&nbsp; $n = 2$.
 
*The memory&nbsp; $m$&nbsp; and the influence length&nbsp; $\nu$&nbsp; are different &nbsp; &#8658; &nbsp; <u>Answers 3 and 4</u>.


'''(2)'''&nbsp; The shift register of encoder &nbsp;$\rm A$&nbsp; does contain two memory cells.&nbsp; However,&nbsp; since&nbsp; $x_i^{(1)} = u_i$&nbsp; and&nbsp; $x_i^{(2)} = u_i + u_{i-1}$&nbsp; is influenced only by the immediately preceding bit&nbsp; $u_{i-1}$&nbsp; besides the current information bit&nbsp; $u_i$, 
[[File:EN_KC_A_3_1.png|right|frame|Equivalent encoder representations]]
*the memory is&nbsp; $m = 1$,&nbsp; and
 
*the influence length is&nbsp; $\nu = m + 1 = 2$.


The graphic shows the two encoders in another representation,&nbsp; whereby the&nbsp; "memory cells"&nbsp; are highlighted in yellow. 
*For the encoder &nbsp;$\rm A$&nbsp; one recognizes only one memory &#8658; $m = 1$.
 
*In contrast,&nbsp; for the encoder &nbsp;$\rm B$&nbsp; actually&nbsp; $m = 2$&nbsp; and&nbsp; $\nu = 3$.

*Thus,&nbsp; the&nbsp; <u>proposed solution 2</u>&nbsp; is correct.



'''(3)'''&nbsp; For the upper output of encoder &nbsp;$\rm B$&nbsp; applies in general:
:$$x_i^{(1)} = u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm}.$$

*Considering the preassignment&nbsp;($(u_0 = u_{-1} = 0)$,&nbsp; we obtain with the above data:
:$$x_1^{(1)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_{1} + u_{0}+ u_{-1} = 1+0+0 = 1 \hspace{0.05cm},\hspace{1cm}x_2^{(1)} = u_{2} + u_{1}+ u_{0} = 0+1+0 = 1\hspace{0.05cm},$$
:$$x_3^{(1)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_{3} + u_{2}+ u_{1} \hspace{0.25cm}= 1+0+1 = 0 \hspace{0.05cm},\hspace{1cm}x_4^{(1)} = u_{4} + u_{3}+ u_{2} = 1+1+0 = 0\hspace{0.05cm},$$
:$$x_5^{(1)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} u_{5} + u_{4}+ u_{3} \hspace{0.25cm}= 0+1+1 = 0 \hspace{0.05cm},\hspace{1cm}x_6^{(1)} = u_{6} + u_{5}+ u_{4} = 0+0+1 = 1\hspace{0.05cm},$$
:$$x_7^{(1)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x_8^{(1)} = \text{...} \hspace{0.05cm}= 0 \hspace{0.05cm}.$$

*The&nbsp; <u>proposed solution 1</u>&nbsp; is correct.&nbsp; The second solution suggestion &nbsp; &#8658; &nbsp; $\underline {x}^{(1)} = \underline {u}$&nbsp; would only be valid for a systematic code&nbsp; $($which is not present here$)$.


'''(4)'''&nbsp; Analogous to subtask&nbsp; '''(3)'''&nbsp; &rArr; &nbsp; $x_i^{(2)} = u_i + u_{i&ndash;2}$:
:$$x_1^{(2)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}   1+0 = 1 \hspace{0.05cm},\hspace{0.2cm}x_2^{(2)} = 0+0 = 0\hspace{0.05cm},
\hspace{0.2cm}x_3^{(3)} = 1+1 = 0\hspace{0.05cm},\hspace{0.2cm}x_4^{(2)} =  1+0 = 1 \hspace{0.05cm},$$
:$$x_5^{(2)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0+1 = 1\hspace{0.05cm},
\hspace{0.2cm}x_6^{(2)} = 0+1 = 1\hspace{0.05cm},\hspace{0.2cm} 
x_7^{(2)} = x_8^{(2)} = \text{...} \hspace{0.05cm}= 0 \hspace{0.05cm}.$$

*The correct solution is the&nbsp; <u>proposed solution 2</u>.



'''(5)'''&nbsp; For the&nbsp; $($entire$)$&nbsp; code sequence,&nbsp; one can formally write:
:$$\underline{\it x} =  \big( \hspace{0.05cm}\underline{\it x}_1\hspace{0.05cm}, \hspace{0.05cm} \underline{\it x}_2\hspace{0.05cm}, \hspace{0.05cm}\text{...}\hspace{0.05cm}  \underline{\it x}_i \hspace{0.05cm}, \text{...} \hspace{0.05cm} \big )\hspace{0.05cm}, \hspace{0.3cm}  \underline{\it x}_i = \big( x_i^{(1)}\hspace{0.05cm}, x_i^{(2)} \big)
\hspace{0.4cm}\Rightarrow \hspace{0.4cm} \underline{\it x} =  \big( \hspace{0.05cm}x_1^{(1)}\hspace{0.01cm},\hspace{0.05cm} x_2^{(1)}\hspace{0.01cm},\hspace{0.05cm} x_1^{(2)}\hspace{0.01cm},\hspace{0.05cm} x_2^{(2)}\hspace{0.01cm}, \hspace{0.05cm} \text{...} \hspace{0.05cm} \big )\hspace{0.05cm}. $$

*A comparison with the solutions of subtasks&nbsp; '''(3)'''&nbsp; and&nbsp; '''(4)'''&nbsp; shows the correctness of the&nbsp; <u>proposed solution 1</u>.
{{ML-Fuß}}


[[Category:Channel Coding: Exercises|^3.1 Basics of Convolutional Coding^]]