C/C++ 编程实现 LTE Turbo编码

weixingguang

C/C++ 编程实现 LTE Turbo编码

博客源地址http://blog.csdn.net/jxwxg/article/details/53644821。更多SDR，LTE博客请点击http://blog.csdn.net/jxwxg。

在LTE协议TS 136 212中详细介绍了LTE里面Turbo编码的算法。但协议看起来实在是太晦涩难懂，本文档通俗地介绍LTE中Turbo编码的原理，并用C语言编程实现了一个LTE Turbo编码器。


一、 Turbo编码器

LTE系统采用的1/3码率的Turbo编码器，即1个输入比特会对应3个输出比特，即Xk，Zk，Z’k。其中，Xk叫做系统比特，Xk与输入的比特相等。Zk和Z’k叫做冗余比特，Zk对应编码器1的输出，Z’k对应编码器2的输出，冗余比特用来增强传输的可靠性。
图中每个编码器的输入端都有一个单刀双掷开关，当正常编码时，开关与输入连接。当没有输入，正在添加尾比特时，开关与输入断开。
下面以编码器1来介绍Turbo编码的原理。
首先，三个寄存器（D1，D2，D3）初始化为0。输入比特Ck=1，此时有Xk=1。输入第一个寄存器的值为D2 +D3 +Ck。第一个编码器输出的值为 D1的输入值+D1的输出值+D3的输出值，即Zk=D2 +D3 +Ck + D1+D3。
此次编码完成后，寄存器的值往后推。即D3的值更新为D2的输出，D2的值更新为D1的输出，D1的值更新为D1的输入值，即D2 +D3 +Ck。
编码器2的原理与编码器1类似，输入比特进入编码器2前需要先进行交织，即把位置打乱。交织具体的原理将在下一章介绍。




最后，当所有的输入比特都编码完成时，需要把开关与输入断开连接以对编码后的比特添加尾比特。尾比特是为了让编码器回到初始状态，避免了两个码字之间的关联性。协议定义了一共添加12bit的尾比特，12比特具体的值如下图所示。下图应该按照从上到下，从左往右的顺序看，即先看d(k)，接着看d(k+1)，d(k+2), d(k+3)。Xk，Zk，Z’k与上述定义相同，而X’k对应图中最底下的虚线。



如果系统输入c0，c1，则编码后会输出c0，z(0)，z’(0)，c1, z(1)，z’(1)，d(k)(0)，d(k)(1), d(k)(2), d(k+1)(0)，d(k+1)(1), d(k+1)(2), d(k+2)(0)，d(k+2)(1), d(k+2)(2)。


二、 Turbo交织

如果输入的比特为c0，c1……ci……c(K-1)，输出的比特为c’0，c’1……c’j……c’(K-1)，则j=(f1*i + f2*i*i) mod K。
f1，f2和K的定义在LTE协议里面有一个对应的表格，一共188组。编码的时候根据表格找到大于编码输入长度的最小的K值。




三、 C编程实现Turbo编码器

如果看了上述介绍还是不理解LTE Turbo编码的原理，那么就直接show you the code。对照C语言实现的Turbo编码器更容易理解Turbo编码的原理。

1. #include <stdio.h>
   
2. #include <stdint.h>
   
3. #include <stdlib.h>
   
4. #include <string.h>
   
5. 
   
6. #define NOF_REGS 3
   
7. #define NOF_TAILINGS 12
   
8. #define MAX_CB_SIZE 188
   
9. #define MAX_BIT_LENGTH 6144
   
10. 
    
11. const uint32_t tc_cb_sizes[MAX_CB_SIZE] = {
    
12. 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120,      
    
13. 128, 136, 144, 152, 160, 168, 176, 184, 192, 200, 208, 216, 224, 232,
    
14. 240, 248, 256, 264, 272, 280, 288, 296, 304, 312, 320, 328, 336, 344,
    
15. 352, 360, 368, 376, 384, 392, 400, 408, 416, 424, 432, 440, 448, 456,
    
16. 464, 472, 480, 488, 496, 504, 512, 528, 544, 560, 576, 592, 608, 624,
    
17. 640, 656, 672, 688, 704, 720, 736, 752, 768, 784, 800, 816, 832, 848,
    
18. 864, 880, 896, 912, 928, 944, 960, 976, 992, 1008, 1024, 1056, 1088,
    
19. 1120, 1152, 1184, 1216, 1248, 1280, 1312, 1344, 1376, 1408, 1440, 1472,
    
20. 1504, 1536, 1568, 1600, 1632, 1664, 1696, 1728, 1760, 1792, 1824, 1856,
    
21. 1888, 1920, 1952, 1984, 2016, 2048, 2112, 2176, 2240, 2304, 2368, 2432,
    
22. 2496, 2560, 2624, 2688, 2752, 2816, 2880, 2944, 3008, 3072, 3136, 3200,
    
23. 3264, 3328, 3392, 3456, 3520, 3584, 3648, 3712, 3776, 3840, 3904, 3968,
    
24. 4032, 4096, 4160, 4224, 4288, 4352, 4416, 4480, 4544, 4608, 4672, 4736,
    
25. 4800, 4864, 4928, 4992, 5056, 5120, 5184, 5248, 5312, 5376, 5440, 5504,
    
26. 5568, 5632, 5696, 5760, 5824, 5888, 5952, 6016, 6080, 6144 };
    
27. 
    
28. const uint32_t f1_list[MAX_CB_SIZE] = {
    
29. 3, 7, 19, 7, 7, 11, 5, 11, 7, 41, 103,
    
30. 15, 9, 17, 9, 21, 101, 21, 57, 23, 13, 27, 11, 27, 85, 29, 33, 15, 17, 33,
    
31. 103, 19, 19, 37, 19, 21, 21, 115, 193, 21, 133, 81, 45, 23, 243, 151, 155,
    
32. 25, 51, 47, 91, 29, 29, 247, 29, 89, 91, 157, 55, 31, 17, 35, 227, 65, 19,
    
33. 37, 41, 39, 185, 43, 21, 155, 79, 139, 23, 217, 25, 17, 127, 25, 239, 17,
    
34. 137, 215, 29, 15, 147, 29, 59, 65, 55, 31, 17, 171, 67, 35, 19, 39, 19, 199,
    
35. 21, 211, 21, 43, 149, 45, 49, 71, 13, 17, 25, 183, 55, 127, 27, 29, 29, 57,
    
36. 45, 31, 59, 185, 113, 31, 17, 171, 209, 253, 367, 265, 181, 39, 27, 127,
    
37. 143, 43, 29, 45, 157, 47, 13, 111, 443, 51, 51, 451, 257, 57, 313, 271, 179,
    
38. 331, 363, 375, 127, 31, 33, 43, 33, 477, 35, 233, 357, 337, 37, 71, 71, 37,
    
39. 39, 127, 39, 39, 31, 113, 41, 251, 43, 21, 43, 45, 45, 161, 89, 323, 47, 23,
    
40. 47, 263 };
    
41. 
    
42. const uint32_t f2_list[MAX_CB_SIZE] = {
    
43. 10, 12, 42, 16, 18, 20, 22, 24, 26, 84,
    
44. 90, 32, 34, 108, 38, 120, 84, 44, 46, 48, 50, 52, 36, 56, 58, 60, 62, 32,           
    
45. 198, 68, 210, 36, 74, 76, 78, 120, 82, 84, 86, 44, 90, 46, 94, 48, 98, 40,
    
46. 102, 52, 106, 72, 110, 168, 114, 58, 118, 180, 122, 62, 84, 64, 66, 68, 420,
    
47. 96, 74, 76, 234, 80, 82, 252, 86, 44, 120, 92, 94, 48, 98, 80, 102, 52, 106,
    
48. 48, 110, 112, 114, 58, 118, 60, 122, 124, 84, 64, 66, 204, 140, 72, 74, 76,
    
49. 78, 240, 82, 252, 86, 88, 60, 92, 846, 48, 28, 80, 102, 104, 954, 96, 110,
    
50. 112, 114, 116, 354, 120, 610, 124, 420, 64, 66, 136, 420, 216, 444, 456,
    
51. 468, 80, 164, 504, 172, 88, 300, 92, 188, 96, 28, 240, 204, 104, 212, 192,
    
52. 220, 336, 228, 232, 236, 120, 244, 248, 168, 64, 130, 264, 134, 408, 138,
    
53. 280, 142, 480, 146, 444, 120, 152, 462, 234, 158, 80, 96, 902, 166, 336,
    
54. 170, 86, 174, 176, 178, 120, 182, 184, 186, 94, 190, 480 };
    
55. 
    
56. int search_segment_index(int input_length)
    
57. {
    
58.         int j= 0;
    
59.         while( j < MAX_CB_SIZE && tc_cb_sizes[j] < input_length)
    
60.                 j++;
    
61. 
    
62.         if(j == MAX_CB_SIZE)
    
63.                 return -1;
    
64.         else
    
65.                 return j;
    
66. }
    
67. 
    
68. int turbo_interleaver(uint8_t *interleaver, int input_length)
    
69. {
    
70.         if(input_length > MAX_BIT_LENGTH)
    
71.                 return -1;
    
72. 
    
73.         // Find code block index
    
74.         int segment_index = search_segment_index(input_length);
    
75.         if(segment_index == -1)
    
76.                 return -1;
    
77. 
    
78.         uint32_t f1 = f1_list[segment_index];
    
79.         uint32_t f2 = f2_list[segment_index];
    
80. 
    
81.         uint32_t i = 0, j;
    
82.         for(i = 0; i < input_length; i++)
    
83.         {
    
84.                 j = (f1 * i + f2 * i * 1) % input_length;
    
85.                 interleaver[i] = j;
    
86.         }
    
87. 
    
88.         for(i = input_length; i < MAX_BIT_LENGTH; i++)
    
89.                 interleaver[i] = 0;
    
90. 
    
91.         return 0;
    
92. }
    
93. 
    
94. void lte_turbo(uint8_t *input, uint8_t* output, uint32_t input_length)
    
95. {
    
96. 
    
97.         // Initialization of turbo registers
    
98.         uint8_t reg1_1, reg1_2, reg1_3, reg2_1, reg2_2, reg2_3;
    
99. 
    
100.         reg1_1 = 0;
     
101.         reg1_2 = 0;
     
102.         reg1_3 = 0;
     
103. 
     
104.         reg2_1 = 0;
     
105.         reg2_2 = 0;
     
106.         reg2_3 = 0;
     
107. 
     
108.         // Initialization of turbo interleaver
     
109.         uint8_t* input_interleaver = malloc(MAX_BIT_LENGTH * sizeof(uint8_t));
     
110.         if (turbo_interleaver(input_interleaver, input_length) < 0 )
     
111.         {
     
112.                 printf("Initialization of turbo interleaver ERROR!\n");
     
113.                 exit(-1);
     
114.         }
     
115. 
     
116.         uint32_t k = 0, i, j;
     
117.         uint8_t bit, in, out;
     
118.         for(i = 0; i < input_length; i++)
     
119.         {
     
120.                 bit = input[i];
     
121.                
     
122.                 // X[k]
     
123.                 output[k] = input[i];
     
124.                 k++;
     
125. 
     
126.                 in = bit ^ (reg1_3 ^ reg1_2);
     
127.                 out = reg1_3 ^ (reg1_1 ^ in);
     
128. 
     
129.                 reg1_3 = reg1_2;
     
130.                 reg1_2 = reg1_1;
     
131.                 reg1_1 = in;
     
132. 
     
133.                 // Z[k]
     
134.                 output[k] = out;
     
135.                 k++;
     
136. 
     
137.                 bit = input[input_interleaver[i]];
     
138. 
     
139.                 in = bit ^ (reg2_3 ^ reg2_2);
     
140.                 out = reg2_3 ^ (reg2_1 ^ in);
     
141. 
     
142.                 reg2_3 = reg2_2;
     
143.                 reg2_2 = reg2_1;
     
144.                 reg2_1 = in;
     
145. 
     
146.                 // Z*[k]
     
147.                 output[k] = out;
     
148.                 k++;
     
149.         }
     
150. 
     
151.         k = 3 * input_length;
     
152. 
     
153.         // Tailing coder 1
     
154.         for(j = 0; j< NOF_REGS; j++)
     
155.         {
     
156.                 bit = reg1_3 ^ reg1_2;
     
157. 
     
158.                 output[k] = bit;
     
159.                 k++;
     
160. 
     
161.                 in = bit ^ (reg1_3 ^ reg1_2);
     
162.                 out = reg1_3 ^ (reg1_1 ^ in);
     
163. 
     
164.                 reg1_3 = reg1_2;
     
165.                 reg1_2 = reg1_1;
     
166.                 reg1_1 = in;
     
167. 
     
168.                 output[k] = out;
     
169.                 k++;
     
170.         }
     
171. 
     
172.         // Tailing coder 2
     
173.         for(j = 0; j < NOF_REGS; j++)
     
174.         {
     
175.                 bit = reg2_3 ^ reg2_2;
     
176. 
     
177.                 output[k] = bit;
     
178.                 k++;
     
179. 
     
180.                 in = bit ^ (reg2_3 ^ reg2_2);
     
181.                 out = reg2_3 ^ (reg2_1 ^ in);
     
182. 
     
183.                 reg2_3 = reg2_2;
     
184.                 reg2_2 = reg2_1;
     
185.                 reg2_1 = in;
     
186. 
     
187.                 output[k] = out;
     
188.                 k++;
     
189.         }
     
190. 
     
191.         free(input_interleaver);
     
192. 
     
193. }
     
194. 
     
195. int main(int argc, char* argv[])
     
196. {
     
197.         uint32_t input_length = 100;
     
198.         if(argc == 2)
     
199.                 input_length = atoi(argv[1]);
     
200.         printf("Input bits length %d.\n", input_length);
     
201. 
     
202.         uint32_t output_length = input_length * 3 + NOF_TAILINGS;
     
203.         uint8_t* input = malloc(input_length * sizeof(uint8_t));
     
204.         uint8_t* output = malloc(output_length * sizeof(uint8_t));
     
205. 
     
206.         srand(time(NULL));
     
207.         int i;
     
208.         for(i = 0; i < input_length; i++)
     
209.                 input[i] = rand() % 2;
     
210. 
     
211.         puts("Input Bits :");
     
212.         for(i = 0; i < input_length; i++)
     
213.         {
     
214.                 printf("%d ", input[i]);
     
215.                 if( (i+1) % 20 == 0)
     
216.                         printf("\n");
     
217.         }
     
218.         printf("\n");
     
219. 
     
220.         lte_turbo(input, output, input_length);
     
221. 
     
222.         puts("Output Bits :");
     
223.         for(i = 0; i < output_length; i++)
     
224.         {
     
225.                 printf("%d ", output[i]);
     
226.                 if( (i+1) % 20 == 0)
     
227.                         printf("\n");
     
228.         }
     
229. 
     
230.         printf("\n");
     
231. 
     
232.         free(input);
     
233.         free(output);
     
234.         return 0;
     
235. }

复制代码

编译
gcc turbo.c -o turbo

运行 参数为输入Bit长度。LTE规定当输入bit长度大于6144时，需要对bit进行分割，本代码没有实现这部分功能。
./turbo 200

四 、备注


上述代码效率较低，如果要编写更高效的Turbo编码器，可以使用查表的算法或者使用SSE、AVX等指令集。