CN1756091A

CN1756091A - A turbo code interleaver and its interleaving method

Info

Publication number: CN1756091A
Application number: CN 200410080398
Authority: CN
Inventors: 赵训威
Original assignee: PUTIAN INST OF INFORMATION TECHNOLOGY
Current assignee: China Potevio Co ltd; Petevio Institute Of Technology Co ltd
Priority date: 2004-09-29
Filing date: 2004-09-29
Publication date: 2006-04-05
Anticipated expiration: 2024-09-29
Also published as: CN100477538C

Abstract

The invention discloses a Turbo code interlace device and the interlacing method. Wherein, said interlace device comprises: a initialization module, a calculation module, and memory module which comprises a control circuit and a memory for memorizing the effective interlace address; and said method can find the its law based on the study of 3GPP Turbo interlace algorism and solve the defection that processing interlace with looking up table in present technique, therefore, the invention has make the interlace device with a certain flexibility.

Description

A turbo code interleaver and its interleaving method

技术领域technical field

本发明涉及移动通信中的交织技术，具体地说，涉及一种Turbo码交织器及其交织的方法。The present invention relates to interleaving technology in mobile communication, in particular to a Turbo code interleaver and its interleaving method.

背景技术Background technique

Turbo码交织器是Turbo编译码器的重要组成部分，Turbo码具有的优异性能，其根本原因在于Turbo码的实现方案中，交织器实现了伪随机性。在发送端，其伪随机性通过编码器以及并行级联方式来实现；在译码端，则利用具有软输入/软输出特性的交织器的反馈迭代译码来实现。可见，交织器是非常重要的，其性能直接影响Turbo码的性能。3GPP(第三代移动通信伙伴计划)协议给出了一种不规则交织的算法，这种交织器算法非常复杂而且随交织块长度的不同其算法也不同。The Turbo code interleaver is an important part of the Turbo codec. The fundamental reason for the excellent performance of the Turbo code is that the interleaver realizes pseudo-randomness in the implementation of the Turbo code. At the sending end, its pseudo-randomness is realized through encoders and parallel cascading; at the decoding end, it is realized by feedback iterative decoding of an interleaver with soft input/soft output characteristics. It can be seen that the interleaver is very important, and its performance directly affects the performance of the Turbo code. The 3GPP (Third Generation Partnership Project) protocol provides an algorithm for irregular interleaving. This interleaver algorithm is very complex and varies with the length of the interleaving block.

按照3GPP规定，Turbo码的交织包括比特输入矩阵，矩阵的行内交换和行间交换，矩阵中的比特输出时将原来不存在的比特删除。以下说明协议中有关Turbo码的交织过程。According to the 3GPP regulations, the interleaving of Turbo codes includes bit input matrix, intra-row exchange and inter-row exchange of the matrix, and when the bits in the matrix are output, the bits that do not exist before are deleted. The following describes the interleaving process of Turbo codes in the protocol.

设Turbo码的交织输入比特记为x₁，x₂，x₃，...，x_K，K是输入的比特数机交织长度，并且40≤K≤5114。Turbo码交织的输入比特序列x_k按如下步骤写入矩阵。Let the interleaving input bits of the Turbo code be denoted as x ₁ , x ₂ , x ₃ , ..., x _K , where K is the number of input bits and the interleaving length, and 40≤K≤5114. The input bit sequence x _k interleaved by Turbo code is written into the matrix according to the following steps.

(1)确定矩阵的行数R：(1) Determine the number of rows R of the matrix:

$R R = = \{\begin{matrix} 55,, if if ((4040 \leq \leq K K \leq \leq 159159)) \\ 1010,, if if ((((160160 \leq \leq K K \leq \leq 200200)) or or ((481481 \leq \leq K K \leq \leq 530530)))) \\ 2020,, if if ((K K = = any other value any other value)) \end{matrix}$

矩阵的行数由上到下记为0，1，2，...，R-1。The number of rows of the matrix is recorded as 0, 1, 2, ..., R-1 from top to bottom.

(2)确定矩阵的列数C：(2) Determine the number of columns C of the matrix:

其中，p为素数。矩阵的列数从左到右记为0，1，2，...，C-1。Among them, p is a prime number. The number of columns of the matrix is denoted as 0, 1, 2, ..., C-1 from left to right.

(3)将比特序列x_k一行一行的写入R×C矩阵，比特x₁在0行的0列上：(3) Write the bit sequence x _k into the R×C matrix row by row, and the bit x ₁ is on column 0 of row 0:

$[\begin{matrix} {x x}_{11} & {x x}_{22} & {x x}_{33} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {x x}_{C C} \\ {x x}_{((C C + + 11))} & {x x}_{((C C + + 22))} & {x x}_{((C C + + 33))} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {x x}_{22 C C} \\ \cdot &Center Dot; & \cdot &Center Dot; & \cdot &Center Dot; & \cdot &Center Dot; \\ \cdot &Center Dot; & \cdot &Center Dot; & \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \\ \cdot &Center Dot; & \cdot &Center Dot; & \cdot &Center Dot; & \cdot &Center Dot; \\ {x x}_{((((R R - - 11)) C C + + 11))} & {x x}_{((((R R - - 11)) C C + + 22))} & {x x}_{((((R R - - 11)) C C + + 33))} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {x x}_{RC RC} \end{matrix}]$

比特输入R×C矩阵后，矩阵的行间交换和行内交换按以下算法进行：After the bits are input into the R×C matrix, the inter-row exchange and intra-row exchange of the matrix are performed according to the following algorithm:

(1)从表1选择原根v(1) Select the original root v from Table 1

(2)构造行内交换基本序列s(i)(2) Construct the basic sequence s(i) of intra-row exchange

s(i)＝[v×s(i-1)]mod p，i＝1，2，…，(p-2)，and s(0)＝1。s(i)=[v×s(i-1)] mod p, i=1, 2, ..., (p-2), and s(0)=1.

其中i为矩阵列序号。Where i is the matrix column number.

(3)以q₀＝1为{q_j}中的第一个素数，按下式选择连续的最小素数{q_j}(j＝1，2，...，R-1，为矩阵行序号)：(3) With q ₀ =1 as the first prime number in {q _j }, select the continuous minimum prime number {q _j } (j=1, 2, ..., R-1, as the matrix row serial number):

g.c.d{q_j，p-1}＝1，q_j＞6，q_j＞q_(j-1)，其中g.c.d.是最大公约数。gcd{q _j , p-1}=1, q _j >6, q _j >q _(j-1) , where gcd is the greatest common divisor.

(4)变换{q_j}得到交换素数{r_j}(4) Transform {q _j } to get exchange prime {r _j }

r_T(j)＝q_j，j＝0，1，...，R-1，r _T(j) = q _j , j = 0, 1, . . . , R-1,

其中T(j)(j＝0，1，2，...，R-1)是行间交换模式，由下式确定的四种行间交换模式之一：Pat1，Pat2，Pat3和Pat4Wherein T(j) (j=0, 1, 2, ..., R-1) is the interline exchange mode, one of four interline exchange modes determined by the following formula: Pat1, Pat2, Pat3 and Pat4

${{T T ((00)),, T T ((11)),, T T ((22)),, . . . . . .,, T T ((R R - - 11))}} = = \{\begin{matrix} {Pat Pat}_{44} & if if ((4040 \leq \leq K K \leq \leq 159159)) \\ P P {at at}_{33} & if if ((160160 \leq \leq K K \leq \leq 200200)) \\ {Pat Pat}_{11} & if if ((201201 \leq \leq K K \leq \leq 480480)) \\ {Pat Pat}_{33} & if if ((481481 \leq \leq K K \leq \leq 530530)) \\ {Pat Pat}_{11} & if if ((531531 \leq \leq K K \leq \leq 22802280)) \\ {Pat Pat}_{22} & if if ((22812281 \leq \leq K K \leq \leq 24802480)) \\ {Pat Pat}_{11} & if if ((24812481 \leq \leq K K \leq \leq 31603160)) \\ {Pat Pat}_{22} & if if ((31613161 \leq \leq K K \leq \leq 32103210)) \\ {Pat Pat}_{11} & if if ((32113211 \leq \leq K K \leq \leq 51145114)) \end{matrix}$

Pat1，Pat2，Pat3和Pat4分别如下：Pat1, Pat2, Pat3 and Pat4 are as follows:

Pat1：{19，9，14，4，0，2，5，7，12，18，10，8，13，17，3，1，16，6，15，11}Pat1: {19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 10, 8, 13, 17, 3, 1, 16, 6, 15, 11}

Pat2：{19，9，14，4，0，2，5，7，12，18，16，13，17，15，3，1，6，11，8，10}Pat2: {19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 16, 13, 17, 15, 3, 1, 6, 11, 8, 10}

Pat3：{9，8，7，6，5，4，3，2，1，0}Pat3: {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

Pat4：{4，3，2，1，0}Pat4: {4, 3, 2, 1, 0}

(5)第j个(j＝0，1，2，...，R-1)行内交换如下：(5) The jth (j=0, 1, 2, . . . , R-1) intra-row exchange is as follows:

a.如果C＝p，那么a. If C=p, then

U_j(i)＝s([i×r_j]mod(p-1))，i＝0，1，2，...，(p-2)，andU_j(p-1)＝0，U _j (i) = s([i×r _j ] mod (p-1)), i = 0, 1, 2, ..., (p-2), and U _j (p-1) = 0,

其中U_j(i)是第j行经过行内变换后的第i个输出的输入比特的位置。Wherein U _j (i) is the position of the input bit of the i-th output of the j-th row after in-row transformation.

b.如果C＝p+1，那么b. If C=p+1, then

U_j(i)＝s([i×r_j]mod(p-1))，i＝0，1，2，...，(p-2)，U_j(p-1)＝0，and U_j(p)＝p，U _j (i)=s([i×r _j ]mod(p-1)), i=0, 1, 2, . . . , (p-2), U _j (p-1)=0, and U _j (p) = p,

其中U_j(i)是第j行经过行内变换后的第i个输出的输入比特的位置，并where U _j (i) is the position of the input bit of the i-th output of the j-th row after in-row transformation, and

且如果K＝C×R，那么交换U_R-1(p)和U_R-1(0)的位置。And if K=C×R, then swap the positions of UR _-1 (p) and UR _-1 (0).

c.如果C＝p-1，那么c. If C=p-1, then

U_j(i)＝s([i×r_j]mod(p-1))-1，i＝0，1，2，...，(p-2)，U _j (i)=s([i×r _j ]mod(p-1))-1, i=0, 1, 2, . . . , (p-2),

U_j(i)是第j行经过行内交换以后的第i个输出的输入比特的位置。U _j (i) is the position of the input bit of the i-th output after the j-th row undergoes intra-row swapping.

(6)基于模式T(j)(j＝0，1，2，...，R-1)进行行间交换，T(j)是第j个交换行的原始位置。(6) Inter-row exchange is performed based on the pattern T(j) (j=0, 1, 2, . . . , R-1), where T(j) is the original position of the jth exchanged line.

p p v v p p v v p p v v p p v v p p v v 7 7 3 3 47 47 5 5 101 101 2 2 157 157 5 5 223 223 3 3 11 11 2 2 53 53 2 2 103 103 5 5 163 163 2 2 227 227 2 2 13 13 2 2 59 59 2 2 107 107 2 2 167 167 5 5 229 229 6 6 17 17 3 3 61 61 2 2 109 109 6 6 173 173 2 2 233 233 3 3 19 19 2 2 67 67 2 2 113 113 3 3 179 179 2 2 239 239 7 7 23 twenty three 5 5 71 71 7 7 127 127 3 3 181 181 2 2 241 241 7 7 29 29 2 2 73 73 5 5 131 131 2 2 191 191 19 19 251 251 6 6 31 31 3 3 79 79 3 3 137 137 3 3 193 193 5 5 257 257 3 3 37 37 2 2 83 83 2 2 139 139 2 2 197 197 2 2 41 41 6 6 89 89 3 3 149 149 2 2 199 199 3 3 43 43 3 3 97 97 5 5 151 151 6 6 211 211 2 2

表1：素数p和相关的原根vTable 1: Prime number p and related primitive root v

经过行内和行间交换，矩阵的比特记为y′：After intra-row and inter-row exchange, the bits of the matrix are denoted as y′:

$[\begin{matrix} {y the y}^{' '}_{11} & {y the y}^{' '}_{((R R + + 11))} & {y the y}^{' '}_{((22 R R + + 11))} & \cdot &Center Dot; \cdot &Center Dot; \cdot \cdot & {y the y}^{' '}_{((((C C - - 11)) R R + + 11))} \\ {y the y}^{' '}_{22} & {y the y}^{' '}_{((R R + + 22))} & {y the y}^{' '}_{((22 R R + + 22))} & \cdot \cdot \cdot &Center Dot; \cdot &Center Dot; & {y the y}^{' '}_{((((C C - - 11)) R R + + 22))} \\ \cdot &Center Dot; & \cdot \cdot & \cdot &Center Dot; & \cdot &Center Dot; \\ \cdot &Center Dot; & \cdot &Center Dot; & \cdot &Center Dot; & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & \cdot &Center Dot; \\ \cdot &Center Dot; & \cdot &Center Dot; & \cdot \cdot & \cdot \cdot \\ {y the y}^{' '}_{R R} & {y the y}^{' '}_{22 R R} & {y the y}^{' '}_{33 R R} & \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot; & {y the y}^{' '}_{CR CR} \end{matrix}]$

Turbo码交织的输出比特是将经过行内和行间交换的矩阵R×C按列依次输出，起始比特y′₁在0列的0行，结束比特y′_CR在C-1列的R-1行。输出时，将输入序列中不存在的比特去掉，也就是说，对应于x′_k的比特y′_k，如果经过行内和行间交换矩阵中有k＞K的比特y′_k，则在输出时要去掉。交织后的输出记为x′₁，x′₂，...，x′_K，x′₁对应于经过整理的y′_k，k是最小序号，x′₂对应于经过整理的y′_k，k是次小序号。交织的输出比特数为K，需要删除的比特数为R×C-K。The output bits of Turbo code interleaving are to output the matrix R×C that has been exchanged between rows and rows in sequence, the start bit y′ ₁ is in row 0 of column 0, and the end bit y′ _CR is in R- 1 row. When outputting, the bits that do not exist in the input sequence are removed, that is, the bit y′ _k corresponding to x′ _k , if there is a bit y′ _k with k>K in the intra-row and inter-row exchange matrix, then in the output time to remove. The output after interleaving is recorded as x′ ₁ , x′ ₂ , ..., x′ _K , x′ ₁ corresponds to the sorted y′ _k , k is the minimum sequence number, and x′ ₂ corresponds to the sorted y′ _k , k is the next smallest serial number. The number of interleaved output bits is K, and the number of bits to be deleted is R×CK.

上述协议规定的交织算法，在实际的编译码应用中，通常预先根据交织算法生成交织表，通过查表获得用于交织的输入比特和输出比特位置的对应关系，以省去交织过程中复杂的算法。例如，一种方案是，按照协议中规定的所有交织长度，为某些交织长度特别值建立输入比特和输出比特位置的对应关系的位置表，即基本表或交织表，比如分别建立交织长度为40比特、50比特、55比特等的位置表，一般包括220个，进行交织时首先根据交织长度选择对应的位置表，然后根据位置表查找当前输入比特对应的输出比特的位置；另一种方案是，预先估计需要提供的业务类型和交织长度，根据交织长度建立位置表，以减少交织表的存储量，进行交织时直接根据位置表查找当前输入比特对应的输出比特的位置。The interleaving algorithm stipulated in the above protocol, in the actual coding and decoding application, usually generates an interleaving table in advance according to the interleaving algorithm, and obtains the corresponding relationship between the input bit and the output bit position for interleaving by looking up the table, so as to save the complicated interleaving process. algorithm. For example, one solution is to establish a position table corresponding to the position of the input bit and the output bit position for some special values of the interleaving length according to all interleaving lengths specified in the protocol, that is, a basic table or an interleaving table, such as establishing an interleaving length of The position table of 40 bits, 50 bits, 55 bits, etc. generally includes 220. When performing interleaving, first select the corresponding position table according to the interleaving length, and then search for the position of the output bit corresponding to the current input bit according to the position table; another scheme Yes, pre-estimate the service type and interleaving length to be provided, and establish a position table according to the interleaving length to reduce the storage capacity of the interleaving table. When performing interleaving, directly look up the position of the output bit corresponding to the current input bit according to the position table.

无论采用何种方式建立交织表，这种通过查表实现交织的方式在一定程度上可以减少交织算法的运算量，但当交织表的存储量很大，由此所需的查找运算量和查找时间也很大，并且非常不利于硬件的实现。No matter what method is used to establish the interleaving table, this way of realizing interleaving by looking up the table can reduce the amount of calculation of the interleaving algorithm to a certain extent, but when the storage amount of the interleaving table is large, the required search calculation and search The time is also very large, and it is very detrimental to the implementation of the hardware.

发明内容Contents of the invention

有鉴于此，本发明的目的在于提供一种Turbo码交织器，以用硬件电路实现协议中规定的交织算法，避免现有技术中通过查表方式实现交织的缺点；本发明的另一目的在于提供一种Turbo码交织方法，以用于在本发明提供的交织器中实现协议中规定的交织。In view of this, the object of the present invention is to provide a kind of Turbo code interleaver, to realize the interleaving algorithm stipulated in the agreement with the hardware circuit, avoid the shortcoming that realizes interleaving by the look-up table mode in the prior art; Another object of the present invention is A turbo code interleaving method is provided for implementing the interleaving specified in the protocol in the interleaver provided by the present invention.

本发明的交织器通过以下技术方案实现：The interleaver of the present invention is realized through the following technical solutions:

一种Turbo码交织器，其特征在于，所述交织器包括初始化模块，计算模块，以及，包含有控制电路和用于存储有效交织地址的缓存器的缓存模块，来自外部的时钟信号分别送至上述模块，其中，A kind of Turbo code interleaver, it is characterized in that, described interleaver comprises initializing module, computing module, and, comprises the buffering module of control circuit and the buffer memory that is used to store effective interleaving address, the clock signal from outside is sent to respectively The above modules, where,

初始化模块接收到来自外部的初始化启动信号后，根据当前业务的交织长度从外部存储器读取比特输入矩阵的行数、列数、素数和原根，根据读取的上述参数计算当前业务的所有行内交换基本序列并存储，向外部输出初始化结束标志，且向计算模块输出包括交织长度、行数、列数以及素数的参数组和用于读取行内交换模式和交换素数的基地址；After the initialization module receives the initialization start signal from the outside, it reads the row number, column number, prime number and original root of the bit input matrix from the external memory according to the interleaving length of the current business, and calculates all the in-line data of the current business according to the above parameters read. The basic sequence is exchanged and stored, and the initialization end flag is output to the outside, and the parameter group including the interleaving length, the number of rows, the number of columns, and the prime number and the base address for reading the intra-row exchange mode and the exchange prime number are output to the calculation module;

计算模块接收到外部模块根据初始化模块输出的初始化结束标志而产生的启动信号后，根据当前行序号和初始化模块输出的基地址，计算用于读取存储于外部存储器的读取行内交换模式和交换素数的读地址，根据读地址读取行内交换模式和交换素数，并读取来自外部的正逆序标志以及存储于初始化模块中的行内交换基本序列，根据读取的行内交换模式、交换素数以及行内交换基本序列，按列数和素数的关系，选择以下公式计算比特输入矩阵的第j行第i列对应的交织地址：After the calculation module receives the start signal generated by the external module according to the initialization end flag output by the initialization module, it calculates the in-line exchange mode and exchange mode for reading stored in the external memory according to the current row number and the base address output by the initialization module. The read address of the prime number, read the in-line exchange mode and exchange prime number according to the read address, and read the forward and reverse order signs from the outside and the in-line exchange basic sequence stored in the initialization module, according to the read in-line exchange mode, exchange prime number and in-line exchange Exchange the basic sequence, and select the following formula to calculate the interleaving address corresponding to the jth row and ith column of the bit input matrix according to the relationship between the number of columns and the prime number:

如果列数和素数相等，则If the number of columns and primes are equal, then

$intterleaver interleaver__address address = = \{\begin{matrix} T T ((j j)) * * C C + + s the s ((((i i * * {r r}_{T T ((j j))})) mod mod ((p p - - 11)))),, [[i i = = 00,, . . . . . .,, p p - - 22;; j j = = 00,, . . . . . .,, R R - - 11]] \\ T T ((j j)) * * C C,, [[i i = = p p - - 11;; j j = = 00,, . . . . . .,, R R - - 11]] \end{matrix} - - - - - - ((a a))$

如果列数等于素数与1之和，则将交织长度与比特输入矩阵的行数和列数之积进行比较，如果不相等，则按式(b)计算，如果相等，则按式(c)计算，If the number of columns is equal to the sum of the prime number and 1, then the interleaving length is compared with the product of the number of rows and the number of columns of the bit input matrix, if not equal, then calculate according to formula (b), if equal, then according to formula (c) calculate,

$intterleaver interleaver__address address = = \{\begin{matrix} T T ((j j)) * * C C + + s the s ((((i i * * {r r}_{T T ((j j))})) mod mod ((p p - - 11)))),, [[i i = = 00,, . . . . . .,, p p - - 22;; j j = = 00,, . . . . . .,, R R - - 11]] \\ T T ((j j)) * * C C,, [[i i = = p p - - 11;; j j = = 00,, . . . . . .,, R R - - 11]] \\ T T ((j j)) * * C C + + p p,, [[i i = = p p;; j j = = 00,, . . . . . .,, R R - - 11 \end{matrix} - - - - - - ((b b))$

$intterleaver intterleaver__address address = = \{\begin{matrix} T T ((j j)) * * C C + + p p,, [[i i = = 00;; j j = = 00,, . . . . . .,, R R - - 11]] \\ T T ((j j)) * * C C + + s the s ((((i i * * {r r}_{T T ((j j))})) mod mod ((p p - - 11)))),, [[i i = = 11,, . . . . . .,, p p - - 22;; j j = = 00,, . . . . . .,, R R - - 11]] \\ T T ((j j)) * * C C,, [[i i = = p p - - 11;; j j = = 00,, . . . . . .,, R R - - 11]] \\ T T ((j j)) * * C C + + 11,, [[i i = = p p;; j j = = 00,, . . . . . .,, R R - - 11]] \end{matrix} - - - - - - ((c c))$

如果列数等于素数与1之差，则If the number of columns is equal to the difference between a prime number and 1, then

intterleaver_address＝T(j)*C+s((i*r_T(j))mod(p-1))-1，[i＝0，...，p-2；j＝0，...，R-1] (d)intterleaver_address=T(j)*C+s((i*r _T(j) )mod(p-1))-1, [i=0,...,p-2; j=0,... , R-1] (d)

其中，T(j)为行间交换模式，C为比特输入矩阵的列数，R为比特输入矩阵的行数，p为素数，s((i*r_T(j)mod(p-1))为行内交换的基本序列，r_T(j)为交换素数；Among them, T(j) is the inter-row exchange mode, C is the number of columns of the bit input matrix, R is the number of rows of the bit input matrix, p is a prime number, s((i*r _T(j) mod(p-1) ) is the basic sequence of intra-row exchange, and r _T(j) is the exchange prime number;

所述计算模块在计算交织地址后，将有效交织地址标志、计算出的交织地址以及开始存储控制信号输出至缓存模块中的控制电路；After the calculation module calculates the interleaving address, it outputs the effective interleaving address flag, the calculated interleaving address and the start storage control signal to the control circuit in the cache module;

缓存模块中的控制电路根据来自外部的所述启动信号、开始存储控制信号以及有效交织地址标志，向用于存储有效交织地址的缓存器输出写使能信号，并输出写地址和读地址至所述缓存器；缓存器受控制电路的控制，将来自计算模块输出的交织地址中的有效交织地址写入，并按照外部模块的读时序要求输出缓存于所述缓存器的交织地址。The control circuit in the cache module outputs a write enable signal to the buffer memory for storing the effective interleave address according to the start signal from the outside, the start storage control signal and the effective interleave address flag, and outputs the write address and the read address to all the buffer; the buffer is controlled by the control circuit, writes the effective interleaving address from the interleaving address output by the calculation module, and outputs the interleaving address buffered in the buffer according to the read timing requirement of the external module.

本发明的交织方法通过以下技术手段实现：The interweaving method of the present invention is realized by the following technical means:

一种Turbo码交织方法，其特征在于，该方法包括，A Turbo code interleaving method, characterized in that the method comprises,

A)根据交织长度读取比特输入矩阵的行数和列数；根据读取的素数和原根计算行内交换基本序列，并存储；初始化比特输入矩阵的行序号和列序号；A) read the number of rows and the number of columns of the bit input matrix according to the interleaving length; calculate the exchange basic sequence in the row according to the read prime number and the original root, and store; initialize the row number and the column number of the bit input matrix;

B)将列数和素数进行比较，B) Comparing column numbers with prime numbers,

如果列数和素数相等，则读取行间交换模式和交换素数，按式(a)计算比特输入矩阵的第j行第i列对应的交织地址，If the number of columns is equal to the prime number, then read the inter-row exchange mode and the exchange prime number, and calculate the interleaving address corresponding to the jth row i column of the bit input matrix according to formula (a),

$intterleaver intterleaver__address address = = \{\begin{matrix} T T ((j j)) * * C C + + s the s ((((i i * * {r r}_{T T ((j j))})) mod mod ((p p - - 11)))),, [[i i = = 00,, . . . . . .,, p p - - 22;; j j = = 00,, . . . .,, R R - - 11]] \\ T T ((j j)) * * C C,, [[i i = = p p - - 11;; j j = = 00,, . . . . . .,, R R - - 11]] \end{matrix} - - - - - - ((a a))$

如果列数等于素数与1之和，则将交织长度与比特输入矩阵的行数和列数之积进行比较，如果不相等，则读取行间交换模式和交换素数，按式(b)计算比特输入矩阵的第j行第i列对应的交织地址，如果相等，则按式(c)计算所述的交织地址，If the number of columns is equal to the sum of the prime number and 1, then compare the interleaving length with the product of the number of rows and the number of columns of the bit input matrix, if not equal, read the inter-row exchange mode and the exchange prime number, and calculate according to formula (b) The interleaving address corresponding to the i column of the jth row of the bit input matrix, if equal, then calculate the described interleaving address according to formula (c),

$intterleaver interleaver__address address = = \{\begin{matrix} T T ((j j)) * * C C + + s the s ((((i i * * {r r}_{T T ((j j))})) mod mod ((p p - - 11)))),, [[i i = = 00,, . . . . . .,, p p - - 22;; j j = = 00,, . . . . . .,, R R - - 11]] \\ T T ((j j)) * * C C,, [[i i = = p p - - 11;; j j = = 00,, . . . . . .,, R R - - 11]] \\ T T ((j j)) * * C C + + p p,, [[i i = = p p;; j j = = 00,, . . . . . .,, R R - - 11]] \end{matrix} - - - - - - ((b b))$

如果列数等于素数与1之差，则读取行间交换模式和交换素数，按式(d)计算比特输入矩阵的第j行第i列对应的交织地址，If the column number is equal to the difference between the prime number and 1, then read the inter-row exchange mode and the exchange prime number, and calculate the interleaving address corresponding to the jth row i column of the bit input matrix according to formula (d),

其中，T(j)为行间交换模式，C为比特输入矩阵的列数，R为比特输入矩阵的行数，p为素数，s((i*r_T(j)mod(p-1))为行内交换基本序列，r_T(j)为交换素数；Among them, T(j) is the inter-row exchange mode, C is the number of columns of the bit input matrix, R is the number of rows of the bit input matrix, p is a prime number, s((i*r _T(j) mod(p-1) ) is the basic sequence of intra-row exchange, and r _T(j) is the exchange prime number;

C)比较当前计算出的交织地址与交织长度，如果计算出的交织地址大于交织长度，则禁止输出当前计算的交织地址，否则输出当前计算出的交织地址。C) Comparing the currently calculated interleaving address with the interleaving length, if the calculated interleaving address is greater than the interleaving length, prohibit outputting the currently calculated interleaving address, otherwise output the currently calculated interleaving address.

本发明在对3GPP Turbo交织算法进行研究的基础上找出其中的规律，针对列数与素数、交织长度与列数与行数之积的关系的几类情况，给出交织前后地址的映射关系，极大地节省了存储空间，优化了交织算法。根据上述交织地址的计算规律以及Turbo编译码器的时序要求，从而对交织器的硬件电路进行了设计，提出了其硬件实现方案。相对于现有技术中以查表进行交织的方式而言，本发明提供的交织方法和交织器，由于其参数可以通过设置以适应不同业务的需要，因此具有一定的灵活性，且占用的存储空间少；并且通过正逆序标志对交织器中计算模块的控制，使得交织地址的正序计算和逆序计算可共用同一个硬件结构，更适合于Turbo码编译码算法的硬件实现，尤其是ASIC实现。The present invention finds out the law on the basis of research on the 3GPP Turbo interleaving algorithm, and provides the mapping relationship of addresses before and after interleaving for several types of relations between the column number and the prime number, the interleaving length, and the product of the column number and the row number , which greatly saves storage space and optimizes the interleaving algorithm. According to the calculation rules of the above-mentioned interleaving address and the timing requirements of the Turbo codec, the hardware circuit of the interleaver is designed, and its hardware implementation scheme is proposed. Compared with the method of interleaving by looking up tables in the prior art, the interleaving method and interleaver provided by the present invention have certain flexibility because their parameters can be set to meet the needs of different services, and the occupied memory Less space; and through the control of the calculation module in the interleaver through the forward and reverse order flags, the forward and reverse order calculations of the interleaving address can share the same hardware structure, which is more suitable for the hardware implementation of Turbo code encoding and decoding algorithms, especially ASIC implementation .

附图说明Description of drawings

图1a和图1b为计算正序交织地址的流程图。Figure 1a and Figure 1b are flow charts for calculating positive sequence interleaving addresses.

图2示出了Turbo码交织器的总体框图。Figure 2 shows a general block diagram of a Turbo code interleaver.

图3示出了计算模块硬件原理图。Fig. 3 shows the schematic diagram of the hardware of the computing module.

图4为乘除法运算流水线示意图。FIG. 4 is a schematic diagram of a multiplication and division operation pipeline.

图5示出了缓存模块电路原理图。FIG. 5 shows a schematic diagram of a cache module circuit.

图6为交织器输入输出的时序关系图。FIG. 6 is a timing relationship diagram of the input and output of the interleaver.

图7为写时序和读时序相同时缓存模块电路原理图。FIG. 7 is a circuit schematic diagram of the cache module when the write timing and the read timing are the same.

具体实施方式Detailed ways

本发明通过对3GPP协议规定的交织方法的总结和归纳，得到在不同交织长度下，比特输入矩阵中各比特在交织后所对应的输出比特序列中的位置，即，得到交织前后地址的映射关系。具体方法如下：By summarizing and summarizing the interleaving method stipulated in the 3GPP protocol, the present invention obtains the position in the output bit sequence corresponding to each bit in the bit input matrix after interleaving under different interleaving lengths, that is, obtains the mapping relationship of addresses before and after interleaving . The specific method is as follows:

首先，根据当前比特输入矩阵中矩阵列数选择相应的计算式，计算矩阵中第j行第i列的输入比特对应的输出比特序列中的位置，即交织地址；First, select the corresponding calculation formula according to the number of matrix columns in the current bit input matrix, and calculate the position in the output bit sequence corresponding to the input bit in the jth row and i column in the matrix, that is, the interleaving address;

(1)当C＝p时，(1) When C=p,

$intterleaver interleaver__address address = = \{\begin{matrix} T T ((j j)) * * C C + + s the s ((((i i * * {r r}_{T T ((j j))})) mod mod ((p p - - 11)))),, [[i i = = 00,, . . . . . .,, p p - - 22;; j j = = 00,, . . . . . .,, R R - - 11]] & ((11)) \\ T T ((j j)) * * C C,, [[i i = = p p - - 11;; j j = = 00,, . . . . . .,, R R - - 11]] & ((22)) \end{matrix}$

(2)当C＝p+1时(2) When C=p+1

a.若K≠C×Ra. If K≠C×R

$intterleaver intterleaver - - address address = = \{\begin{matrix} T T ((j j)) * * C C + + s the s ((((i i * * {r r}_{T T ((j j))})) mod mod ((p p - - 11)))),, [[i i = = 00,, . . . . . .,, p p - - 22;; j j = = 00,, . . . . . .,, R R - - 11]] & ((44)) \\ T T ((j j)) * * C C,, [[i i = = p p - - 11;; j j = = 00,, . . . . . .,, R R - - 11]] & ((55)) \\ T T ((j j)) * * C C + + p p,, [[i i = = p p;; j j = = 00,, . . . . . .,, R R - - 11]] & ((66)) \end{matrix}$

b.若K＝C×Rb. If K=C×R

$intterleaver intterleaver__$ $address address = =$ $\{\begin{matrix} T T ((j j)) * * C C + + p p,, [[i i = = 00;; j j = = 00,, . . . . . .,, R R - - 11]] & ((77)) \\ T T ((j j)) * * C C + + s the s ((((i i * * {r r}_{T T ((j j))})) mod mod ((p p - - 11)))),, [[i i = = 11,, . . . . . .,, p p - - 22;; j j = = 00,, . . . . . .,, R R - - 11]] & ((88)) \\ T T ((j j)) * * C C,, [[i i = = p p - - 11;; j j = = 00,, . . . .,, R R - - 11]] & ((99)) \\ T T ((j j)) * * C C + + 11,, [[i i = = p p;; j j = = 00,, . . . . . .,, R R - - 11]] & ((1010)) \end{matrix}$

(3)当C＝p-1时(3) When C=p-1

intterleaver_address＝T(j)*C+s((i*r_T(j))mod(p-1))-1，[i＝0，...，p-2；j＝0，...，R-1]intterleaver_address=T(j)*C+s((i*r _T(j) )mod(p-1))-1, [i=0,...,p-2; j=0,... , R-1]

然后，比较计算的交织地址与交织长度，如果交织地址大于交织长度，则去掉该交织地址。Then, compare the calculated interleaving address with the interleaving length, and if the interleaving address is greater than the interleaving length, remove the interleaving address.

图1a和图1b为计算正序交织地址的流程图。从流程图可见，计算以i作为外循环(i＝0，…，C-1)，以j作为内循环(j＝0，...，R-1)，对第(2)种情况，即C＝p+1，当K＝C×R时，是一种特殊情况，在3GPP协议中规定要将U_R-1(p)和U_R-1(0)的位置进行交换，而在本发明中通过计算公式可以得到。如果计算逆序交织地址，只需在初始化时将行序号和列序号分别设为R-1和C-1，流程中行序号和列序号按递减变化。Figure 1a and Figure 1b are flow charts for calculating positive sequence interleaving addresses. As can be seen from the flowchart, the calculation takes i as the outer loop (i=0,...,C-1), and j as the inner loop (j=0,...,R-1), for the (2) case, That is, C=p+1, when K=C×R, it is a special case, it is stipulated in the 3GPP agreement that the positions of UR _-1 (p) and _UR-1 (0) should be exchanged, and in In the present invention, it can be obtained through a calculation formula. If the reverse order interleaving address is calculated, it is only necessary to set the row number and the column number to R-1 and C-1 respectively during initialization, and the row number and the column number change in descending order during the process.

上述交织地址的计算方法可采用硬件电路实现。参见图2所示，图2示出了Turbo码交织器的总体框图，包括初始化模块、交织地址计算模块、以及用于进行输入输出速率转换的缓存模块，该缓存模块包含有控制电路和用于存储有效交织地址的缓存器。其中，The calculation method of the above-mentioned interleaving address can be realized by using a hardware circuit. Referring to shown in Figure 2, Figure 2 shows the overall block diagram of the Turbo code interleaver, including an initialization module, an interleaving address calculation module, and a cache module for performing input-output rate conversion, the cache module includes a control circuit and is used for A buffer for storing valid interleaving addresses. in,

初始化模块收到初始化启动信号start_ini后，根据外部模块送来的当前交织长度、业务参数表索引地址，从交织器外部的第一ROM存储器中读取包括素数p、原根v、以及比特输入矩阵列数C、行数R的参数组，并送至计算模块；根据协议标准按读取的参数计算当前业务的所有行内交换基本序列s(i)，并存入初始化模块中的RAM，其中，当C＝p-1时，将计算得到的s(i)的值减1后存入初始化模块中的RAM；当行内交换基本序列计算完毕后，向交织器外部模块输出初始化结束标志flag；将基地址送至计算模块；After the initialization module receives the initialization start signal start_ini, according to the current interleaving length and the index address of the service parameter table sent by the external module, it reads the prime number p, the original root v, and the bit input matrix from the first ROM memory outside the interleaver The parameter group of the number of columns C and the number of rows R is sent to the calculation module; according to the protocol standard, the basic sequence s(i) of all intra-line exchanges of the current business is calculated according to the read parameters, and stored in the RAM in the initialization module, wherein, When C=p-1, store the RAM in the initializing module after the value of s(i) obtained by calculating is subtracted by 1; After the exchange basic sequence calculation in the row is completed, output the initialization end sign flag to the interleaver external module; The base address is sent to the computing module;

当外部模块收到初始化结束标志后，向计算模块和缓存模块中的控制电路发送启动信号start_cp，同时，计算模块读取来自外部的正逆序标志up_down，以确定是按正序还是按逆序计算交织地址；计算模块从交织器外部的第二ROM存储器中读取行间交换模式T(j)和交换素数r_T(j)，根据初始化模块中RAM存储的行内交换基本序列s(i)、读取的T(j)和r_T(j)、以及来自初始化模块的参数组，按C与p的关系选择相应的计算公式计算输出序列的交织地址，并向缓存模块输出该交织地址以及控制信号，其中控制信号包括开始存储控制信号start_save以及有效交织地址标志valid_flag；When the external module receives the initialization end flag, it sends the start signal start_cp to the control circuit in the computing module and the cache module, and at the same time, the computing module reads the positive and negative sequence flag up_down from the outside to determine whether to calculate the interleaving in the positive sequence or in the reverse sequence Address; the calculation module reads the inter-row exchange mode T(j) and the exchange prime number r _T(j) from the second ROM memory outside the interleaver, and exchanges the basic sequence s(i) and reads according to the inter-row exchange basic sequence s(i) stored in the RAM in the initialization module Take the T(j) and r _T(j) and the parameter group from the initialization module, select the corresponding calculation formula according to the relationship between C and p to calculate the interleaving address of the output sequence, and output the interleaving address and control signal to the cache module , wherein the control signal includes the start storage control signal start_save and the effective interleaving address flag valid_flag;

缓存模块的控制电路在来自外部的所述启动信号、开始存储控制信号以及有效交织地址标志的控制下，向用于存储有效交织地址的缓存器输出写使能信号，将计算出的交织地址中的有效效地址写入缓存器，缓存器在读时序的控制下输出写入的交织地址；并在写时序和外部模块的读时序不相同时，如果写地址等于写地址阈值，则向计算模块输出停止计算信号stop_work有效以停止交织地址的计算，并停止写操作，如果读地址等于读地址阈值，则向计算模块输出停止计算信号stop_work无效，以启动交织地址的计算并启动写操作。The control circuit of the cache module outputs the write enable signal to the buffer for storing the effective interleaving address under the control of the start signal from the outside, the start storage control signal and the effective interleaving address flag, and the calculated interleaving address The effective address of the buffer is written into the buffer, and the buffer outputs the written interleaved address under the control of the read timing; and when the write timing is different from the read timing of the external module, if the write address is equal to the write address threshold, then output to the computing module The stop calculation signal stop_work is valid to stop the calculation of the interleaved address and stop the write operation. If the read address is equal to the read address threshold, the stop calculation signal stop_work is output to the calculation module to be invalid to start the calculation of the interleaved address and start the write operation.

以下以Turbo码编译码器要求交织器每4个时钟周期输出一个交织地址为例，描述上述各模块的电路原理。The circuit principles of the above-mentioned modules are described below by taking the turbo codec as an example requiring the interleaver to output an interleaving address every 4 clock cycles.

参见图3所示，图3示出了计算模块硬件原理图。来自缓存模块的停止计算信号stop_work以及外部的start_cp信号送至具有三个状态的第一状态机的使能端，所述状态机实质为3进制的计数器。当stop_work信号无效且start_cp信号有效时，第一状态机开始计数输出，以向计算模块中行计数器、列计数器、各锁存器、以及输出延迟单元提供时钟信号。地址计算单元根据来自初始化模块的基地址和行计数器输出的行序号j，计算行间交换模式T(j)和交换素数rT(j)对应的存储地址，向第二ROM存储器的读地址端输出该地址，第二存储器根据读地址查找对应的行间交换模式T(j)和交换素数r_T(j)，分别输出至第一乘法器和第二乘法器，其中第一乘法器计算列数C与行间交换模式T(j)的乘积后输出到第一锁存器，第二乘法器计算交换素数r_T(j)与列计数器输出的列序号i的乘积后，输出到第二锁存器。第二锁存器输出至除法器，除法器将第二锁存器的输出与p-1进行模运算，以计算因式(i*r_T(j))mod(p-1)，除法器输出计算结果至第三锁存器。第三锁存器将该计算结果作为读地址输出至存储了行内交换基本序列s(i)的初始化模块中的RAM，该RAM根据读地址输出该地址对应的行内交换基本序列s(i)至复用器，复用器根据列数C与素数p的关系以及当C＝p+1时K与C*R的关系，从复用器的0值、p值、s(i)或1值输入信号中选择满足交织地址计算式的输入信号进行选择性复用，复用后输出至加法器，加法器将来自第一锁存器的计算值与来自选择器的值进行叠加，然后输出至第四锁存器，此时加法器的输出值即为按交织计算公式计算的交织地址。比较器将第四锁存器的输出值和交织长度进行比较，如果第四锁存器的输出值小于等于交织长度，则比较器输出有效交织地址标志valid_flag的有效值至第五锁存器，通过第五锁存器输出，否则，比较器输出有效交织地址标志valid_flag的无效值至第五锁存器。同时，输出延迟单元将来自第四锁存器的交织地址延迟一个时钟周期后输出至缓存模块中的缓存器，即，向缓存模块输出信号cp_output，以使得交织地址的输出与有效交织地址标志valid_flag的输出的时序一致。Referring to FIG. 3 , FIG. 3 shows a hardware schematic diagram of the computing module. The stop calculation signal stop_work from the cache module and the external start_cp signal are sent to the enable terminal of the first state machine with three states, and the state machine is essentially a ternary counter. When the stop_work signal is inactive and the start_cp signal is active, the first state machine starts counting and outputting to provide clock signals to the row counter, column counter, latches, and output delay units in the calculation module. The address calculation unit calculates the storage address corresponding to the inter-row exchange mode T(j) and the exchange prime rT(j) according to the base address from the initialization module and the row number j output by the row counter, and outputs to the read address end of the second ROM memory This address, the second memory looks up the corresponding inter-row exchange mode T(j) and exchange prime number r _T(j) according to the read address, and outputs to the first multiplier and the second multiplier respectively, wherein the first multiplier calculates the number of columns The product of C and the inter-row exchange mode T(j) is output to the first latch, and the second multiplier calculates the product of the exchange prime r _T(j) and the column number i output by the column counter, and then outputs to the second lock memory. The output of the second latch is sent to the divider, and the divider moduloes the output of the second latch with p-1 to calculate the factor (i*r _T(j) )mod(p-1), the divider Output the calculation result to the third latch. The third latch outputs the calculation result as a read address to the RAM in the initialization module that has stored the basic sequence s(i) of the exchange in the row, and the RAM outputs the basic sequence s(i) of the exchange in the row corresponding to the address according to the read address to The multiplexer, the multiplexer is based on the relationship between the column number C and the prime number p and the relationship between K and C*R when C=p+1, from the 0 value, p value, s(i) or 1 value of the multiplexer Among the input signals, the input signals satisfying the interleaving address calculation formula are selected for selective multiplexing, and then output to the adder after multiplexing. The adder superimposes the calculated value from the first latch and the value from the selector, and then outputs to The fourth latch, at this time, the output value of the adder is the interleaving address calculated according to the interleaving calculation formula. The comparator compares the output value of the fourth latch with the interleaving length, and if the output value of the fourth latch is less than or equal to the interleaving length, the comparator outputs the effective value of the effective interleaving address flag valid_flag to the fifth latch, output through the fifth latch, otherwise, the comparator outputs an invalid value of the valid interleaved address flag valid_flag to the fifth latch. At the same time, the output delay unit outputs the interleaved address from the fourth latch to the buffer in the buffer module after one clock cycle delay, that is, outputs the signal cp_output to the buffer module, so that the output of the interleaved address is consistent with the effective interleaved address flag valid_flag The timing of the output is consistent.

在上述计算模块中，各锁存器为了满足交织器的时序要求而引用；行计数器中可以具有分频器，以实现在计算的过程中，以i作为外循环(i＝0，...，c-1)，以j作为内循环(j＝0，...，R-1)计算。来自外部的正逆序标志up_down信号分别输入至行计数器和列计数器的控制端，以控制当进行正序交织地址计算时，行计数器和列计数器采用递增方式计数，当进行逆序交织地址计算时，采用递减方式计数。行计数器和列计数器的输出信号还分别送至控制逻辑，该控制逻辑在计算出交织地址的时序中向缓存模块输出开始存储控制信号start_save。In the above calculation module, each latch is quoted in order to meet the timing requirements of the interleaver; a frequency divider may be provided in the row counter to realize that in the calculation process, i is used as an outer loop (i=0,... , c-1), taking j as the inner loop (j=0, . . . , R-1) for calculation. The positive and negative sequence flag up_down signals from the outside are respectively input to the control terminals of the row counter and the column counter to control the row counter and the column counter to count in increments when performing the forward sequence interleaving address calculation. When performing the reverse sequence interleaving address calculation, use Count down. The output signals of the row counter and the column counter are respectively sent to the control logic, and the control logic outputs the storage start control signal start_save to the cache module at the timing of calculating the interleave address.

最核心部分是乘除器的计算，它将决定交织器的工作速度，在本发明中，使用流水线的方法来完成乘除器的运算，一个乘法器和除法器计算一次(i*r_T(j))mod(p-1)，由于使用第一状态机的状态2来进行锁存、数据的读取，所以乘法和除法的计算都是各用3个时钟周期，乘除法运算的速度均可以满足要求。乘除法运算流水线见图4，这是一个2级流水。采用流水线的方式可以比无流水线方式的速度提高一倍。除法器可以采用EDA综合工具中的库直接生成，不需要自己写VHDL程序，不仅使用方便，而且面积小，功能齐全。The core part is the calculation of multiplier and divider, which will determine the working speed of interleaver. In the present invention, the method of pipeline is used to complete the calculation of multiplier and divider. A multiplier and divider calculate once (i*r _T(j) )mod(p-1), since the state 2 of the first state machine is used for latching and data reading, the calculations of multiplication and division each use 3 clock cycles, and the speed of multiplication and division operations can satisfy Require. The multiplication and division operation pipeline is shown in Figure 4, which is a 2-stage pipeline. The speed of using the pipeline method can be doubled than that of the non-pipeline method. The divider can be directly generated by using the library in the EDA synthesis tool, and there is no need to write a VHDL program by yourself. It is not only easy to use, but also has a small area and complete functions.

参见图5所示，图5示出了缓存模块电路原理图。其中，用于提供写操作地址控制的3进制第三状态机、用于提供读操作地址控制的4进制的第四状态机、写地址计数器、读地址计数器、与门以及停止计算信号产生模块组成了控制电路。来自外部的启动信号start_cp分别输入至第三状态机和第四状态机的计数使能端，时钟信号分别提供给第三状态机、第四状态机、以及用于缓存交织地址的RAM，来自计算模块的开始存储控制信号start_save、来自计算模块的有效交织地址标志valid_flag、以及第三状态机的输出信号输入至与门进行与逻辑运算后输出到缓存交织地址的缓存器的写使能端。第三状态机的输出信号还输出至写地址计数器，第四状态机的输出信号输出至读地址计数器，从而使得写操作每3个时钟执行一次，读操作每4个时钟执行一次。写地址计数器的输出分别输入到缓存交织地址的缓存器的写地址端和停止计算信号产生模块，读地址计数器的输出分别输入到缓存交织地址的缓存器的读地址端和停止计算信号产生模块。停止计算信号产生模块根据输入的写地址判断当前写地址是否等于设定的写地址阈值，如果是，则向计数模块中的第一状态机的计数使能端输出stop_work有效；根据输入的读地址判断当前读地址是否等于设定的读地址阈值，如果是，则向计数模块中的第一状态机的计数使能端输出stop_work无效。来自计数模块中的输出延迟单元的cp_output输出至缓存交织地址的缓存器的数据端。Referring to FIG. 5 , FIG. 5 shows a schematic circuit diagram of a cache module. Among them, the ternary third state machine for providing write operation address control, the quaternary fourth state machine for providing read operation address control, write address counter, read address counter, AND gate and stop calculation signal generation The modules make up the control circuit. The start signal start_cp from the outside is respectively input to the count enable terminal of the third state machine and the fourth state machine, and the clock signal is respectively provided to the third state machine, the fourth state machine, and the RAM for caching the interleaving address, from the calculation The start storage control signal start_save of the module, the valid interleave address flag valid_flag from the calculation module, and the output signal of the third state machine are input to the AND gate for AND logic operation, and then output to the write enable terminal of the buffer that caches the interleave address. The output signal of the third state machine is also output to the write address counter, and the output signal of the fourth state machine is output to the read address counter, so that the write operation is performed once every 3 clocks, and the read operation is performed once every 4 clocks. The output of the write address counter is respectively input to the write address end of the buffer for buffering the interleaving address and the stop calculation signal generation module, and the output of the read address counter is respectively input to the read address end of the buffer for buffering the interleaved address and the stop calculation signal generation module. Stop calculation signal generation module judges whether current write address is equal to the write address threshold value of setting according to the write address of input, if so, then to the counting enable terminal output stop_work of the first state machine in the counting module is effective; According to the read address of input Judging whether the current read address is equal to the set read address threshold, if yes, outputting stop_work to the count enable terminal of the first state machine in the count module is invalid. The cp_output from the output delay unit in the counting module is output to the data end of the buffer for buffering the interleaving address.

从缓存模块的组成可以看出，每三时钟周期向缓存交织地址的缓存器写入一个交织地址，每四个时钟周期从缓存器中读出一个有效交织地址，由于写的速度快，读的速度慢，而存储空间是有限的，并且交织地址的计算是实时的，因此当读写进行到一定程度时，要将计算停下来，待再读出一部分数据后再启动计算，以免交织地址还没有读出来就被覆盖。上述停止计算信号产生模块通过输出stop_work信号来实现读写的控制。It can be seen from the composition of the cache module that an interleaving address is written into the buffer for caching the interleaving address every three clock cycles, and an effective interleaving address is read from the buffer every four clock cycles. Due to the fast writing speed, the read The speed is slow, but the storage space is limited, and the calculation of the interleaving address is real-time. Therefore, when the reading and writing progress to a certain extent, the calculation should be stopped, and the calculation should be started after reading a part of the data to avoid the interleaving address. Overwritten without reading it. The above-mentioned stop calculation signal generation module realizes the control of reading and writing by outputting the stop_work signal.

参见图6所示，图6为交织器输入输出的时序关系图。当start_ini信号有效时，初始化模块开始工作，通过输入的参数组，选择当前业务下相应的参数(包括p，v，R，C)，并实时计算行内交换基本序列s(i)的值，存贮到初始模块内的RAM中，在初始化结束以后，输出一个初始化结束标志flag，反馈给外部模块；当外部模块接收到flag信号后，向计算模块和缓存模块发出start_cp，同时交织器计算模块读外部送来的正逆序标志up_down，并锁入寄存器中，当up_down＝’1’时表示正序，为’0’时表示逆序，于是开始进行交织地址的计算，在start_cp信号有效后的第23个时钟周期开始，每计算出一个交织地址，则输出一个开始存储控制信号start_save。Referring to FIG. 6 , FIG. 6 is a timing relationship diagram of the input and output of the interleaver. When the start_ini signal is valid, the initialization module starts to work, selects the corresponding parameters (including p, v, R, C) under the current business through the input parameter group, and calculates the value of the basic sequence s(i) exchanged in the row in real time, and saves Stored in the RAM in the initial module, after the initialization is completed, an initialization end flag flag is output and fed back to the external module; when the external module receives the flag signal, it sends start_cp to the calculation module and the cache module, and the interleaver calculation module reads The positive and negative sequence flag up_down sent from the outside is locked into the register. When up_down='1', it indicates the positive sequence, and when it is '0', it indicates the reverse sequence. Then the calculation of the interleaving address is started. After the start_cp signal is valid, the 23rd Starting from the first clock cycle, each time an interleaving address is calculated, a start storage control signal start_save is output.

在计算模块中所计算出的交织地址包括有效交织地址和无效交织地址，每三个时钟周期输出一个交织地址。在缓存模块，每3个时钟周期写入一个有效交织地址，每4个时钟周期读出一个有效交织地址。由于无效地址都在比特输入矩阵的第一行，因此至少每隔20个交织地址才会有1个无效交织地址。The interleaving addresses calculated in the calculation module include effective interleaving addresses and invalid interleaving addresses, and an interleaving address is output every three clock cycles. In the cache module, an effective interleaving address is written every 3 clock cycles, and an effective interleaving address is read every 4 clock cycles. Since the invalid addresses are all in the first row of the bit input matrix, at least every 20 interleaving addresses will have one invalid interleaving address.

如果缓存模块中的控制电路在写时序和外部模块的读时序相同时，这时图2所示交织器中，将没有停止计算信号反馈至计算模块，而缓存模块的电路原理如图7所示。控制电路包括，写地址计数器、读地址计数器、与门以及第二状态机，其中，来自外部的所述启动信号输入至第二状态机的使能端，所述时钟信号输入至第二状态机的输入，第二状态机的输出分别连至写地址计数器和读地址计数器的输入，并还输入至与门的输入；来自计算模块的有效交织地址标志以及开始存储控制信号输入至与门的输入，与门的输出连至缓存器的写使能端；写地址计数器输出写地址至缓存器的写地址端，读地址计数器输出读地址至缓存器的读地址端。If the write timing of the control circuit in the cache module is the same as the read timing of the external module, then in the interleaver shown in Figure 2, there will be no stop calculation signal fed back to the calculation module, and the circuit principle of the cache module is shown in Figure 7 . The control circuit includes a write address counter, a read address counter, an AND gate and a second state machine, wherein the start signal from the outside is input to the enabling terminal of the second state machine, and the clock signal is input to the second state machine The input of the second state machine, the output of the second state machine is connected to the input of the write address counter and the read address counter respectively, and is also input to the input of the AND gate; the effective interleaving address flag from the calculation module and the start storage control signal are input to the input of the AND gate , the output of the AND gate is connected to the write enable end of the buffer; the write address counter outputs the write address to the write address end of the buffer, and the read address counter outputs the read address to the read address end of the buffer.

Claims

1, a kind of Turbo code deinterleaving method is characterized in that, this method comprises,

A) read the line number and the columns of bit input matrix according to weaving length; Calculate exchange basic sequence in the row according to prime number that reads and primitive root, and storage; The capable sequence number of initialization bit input matrix and row sequence number;

B) columns and prime number are compared,

If columns and prime number equate, then read in the ranks switch mode and exchange prime number, by the corresponding interleaving address of the capable i row of j of formula (1) calculating bit input matrix,

intterleaver_address = \{\begin{matrix} T (j) * C + s ((i * r_{T (j)}) \mod (p - 1)), [i = 0, . . ., p - 2; j = 0, . . ., R - 1] \\ T (j) * C, [i = p - 1; j = 0, . . ., R - 1] \end{matrix} - - - (1)

If columns equals prime number and 1 sum, then line number and the amassing of columns with weaving length and bit input matrix compares, if it is unequal, then read in the ranks switch mode and exchange prime number, calculate the corresponding interleaving address of the capable i row of j of bit input matrix by formula (2), if equate, then calculate described interleaving address by formula (3)

intterleaver_address = \{\begin{matrix} T (j) * C + s ((i * r_{T (j)}) \mod (p - 1)), [i = 0, . . ., p - 2; j = 0, . . ., R - 1] \\ T (j) * C, [i = p - 1; j = 0, . . ., R - 1] \\ T (j) * C + p, [i = p; j = 0, . . ., R - 1] \end{matrix} - - - (2)

intterleaver_address = \{\begin{matrix} T (j) * C + p, [i = 0; j = 0, . . ., R - 1] \\ T (j) * C + s ((i * r_{T (j)}) \mod (p - 1)), [i = 0, . . ., p - 2, j = 0, . . ., R - 1] \\ T (j) * C, [i = p - 1; j = 0, . . ., R - 1] \\ T (j) * C + 1, [i = p; j = 0, . . ., R - 1] \end{matrix} - - - (3)

If columns equals the poor of prime number and 1, then read in the ranks switch mode and exchange prime number, the capable i of j that calculates the bit input matrix by formula (4) is listed as corresponding interleaving address,

intterleaver_address＝T(j)*C+s((i*r _T(j))mod(p-1))-1，[i＝0，...，p-2；j＝0，...，R-1](4)

Wherein, T (j) is switch mode in the ranks, and C is the columns of bit input matrix, and R is the line number of bit input matrix, and p is a prime number, s ((i*r _{T (j)}Mod (p-1)) is exchange basic sequence in the row, r _{T (j)}Be the exchange prime number;

C) more current interleaving address that calculates and weaving length if the interleaving address that calculates greater than weaving length, then forbids exporting the interleaving address of current calculating, otherwise are exported the current interleaving address that calculates.

2, method according to claim 1, it is characterized in that, described switch mode in the ranks and exchange prime number calculate in advance and are stored in the memory, and the line number of described weaving length, bit input matrix and columns and prime number and primitive root are with the corresponding relation storage of agreement regulation.

3, method according to claim 1, it is characterized in that, the capable sequence number and the row sequence number of described bit input matrix are initialized as 0 respectively, described in the ranks switch mode and the exchange prime number of reading of step B, step by the corresponding interleaving address of the capable i row of j of formula (1) calculating bit input matrix comprises

B01) judge when the prostatitis sequence number whether equal prime number subtract 1 poor, if it is 0 that capable sequence number then is set, execution in step B02 then, otherwise, execution in step B03,

B02) read switch mode in the row of current line correspondence, by formula intterleaver_address=T (j) * C calculates described interleaving address, capable sequence number is set then increases 1, and judge whether work as the prostatitis sequence number equals the poor of line number and 1, if, execution in step C then, otherwise return step B02;

B03) read switch mode and exchange prime number, by formula interleaver_address=T (j) * C+s ((i*r in the row of current line correspondence _{T (j)}Mod (p-1)) calculate described interleaving address, capable sequence number is set then increases 1, and judge whether the current line sequence number equals the poor of line number and 1, if, the row sequence number is set increases 1, return step B01, otherwise, step B03 then returned.

4, method according to claim 1, it is characterized in that, the capable sequence number and the row sequence number of described bit input matrix are initialized as 0 respectively, described in the ranks switch mode and the exchange prime number of reading of step B, step by the corresponding interleaving address of the capable i row of j of formula (2) calculating bit input matrix comprises

B11) judge when the prostatitis sequence number whether equal prime number subtract 1 poor, if, execution in step B12 then, otherwise, execution in step B15 then;

B12) judge whether equal prime number, be 0 if capable sequence number then is set if working as the prostatitis sequence number, execution in step B13 is 0 otherwise capable sequence number is set, then execution in step B14;

B13) read switch mode in the row of current line correspondence, by formula intterleaver_address=T (j) * C+p calculates described interleaving address, capable sequence number is set then increases 1, and judge whether the current line sequence number equals the poor of line number and 1, if, the row sequence number is set increases 1, return step B12, otherwise return step B13;

B14) read switch mode in the row of current line correspondence, by formula intterleaver_address=T (j) * C calculates described interleaving address, capable sequence number is set then increases 1, and judge whether the current line sequence number equals the poor of line number and 1, if, execution in step C then, otherwise, then return step B14;

B15) read switch mode and exchange prime number, by formula intterleaver_address=T (j) * C+s ((i*r in the row of current line correspondence _{T (j)}Mod (p-1)) calculate described interleaving address, capable sequence number is set then increases 1, and judge whether the current line sequence number equals the poor of line number and 1, if, the row sequence number is set increases 1, return step B11, otherwise, step B15 then returned.

5, method according to claim 1, it is characterized in that, the capable sequence number and the row sequence number of described bit input matrix are initialized as 0 respectively, described in the ranks switch mode and the exchange prime number of reading of step B, step by the corresponding interleaving address of the capable i row of j of formula (3) calculating bit input matrix comprises

B20) judge when the prostatitis sequence number whether equal 0, if, execution in step B26 then, otherwise execution in step B21;

B21) judge when the prostatitis sequence number whether equal prime number subtract 1 poor, if, execution in step B22 then, otherwise, execution in step B25 then;

B22) judge whether equal prime number, be 0 if capable sequence number then is set if working as the prostatitis sequence number, execution in step B24 is 0 otherwise capable sequence number is set, then execution in step B23;

B23) read switch mode in the row of current line correspondence, by formula intterleaver_address=T (j) * C calculates described interleaving address, capable sequence number is set then increases 1, and judge whether the current line sequence number equals the poor of line number and 1, if, the row sequence number is set increases 1, return step B22, otherwise return step B23;

B24) read switch mode in the row of current line correspondence, by formula intterleaver_address=T (j) * C+1 calculates described interleaving address, capable sequence number is set then increases 1, and judge whether work as the prostatitis sequence number equals the poor of line number and 1, if, execution in step C then, otherwise, step B24 then returned;

B25) read switch mode and exchange prime number, by formula interleaver_address=T (j) * C+s ((i*r in the row of current line correspondence _{T (j)}Mod (p-1)) calculate described interleaving address, capable sequence number is set then increases 1, and judge whether the current line sequence number equals the poor of line number and 1, if, the row sequence number is set increases 1, return step B21, otherwise, step B25 then returned;

B26) read switch mode in the row of current line correspondence, by formula intterleaver_address=T (j) * C+p calculates described interleaving address, capable sequence number is set then increases 1, and judge whether the current line sequence number equals the poor of line number and 1, if, the row sequence number is set increases 1, return step B20, otherwise, return step B26.

6, method according to claim 1, it is characterized in that, the capable sequence number and the row sequence number of described bit input matrix are initialized as 0 respectively, described in the ranks switch mode and the exchange prime number of reading of step B, step by the corresponding interleaving address of the capable i row of j of formula (4) calculating bit input matrix comprises

B31) judge when the prostatitis sequence number whether equal prime number subtract 1 poor, if, execution in step C then, otherwise, execution in step B32,

B32) read switch mode and exchange prime number, by formula interleaver_address=T (j) * C+s ((i*r in the row of current line correspondence _{T (j)}Mod (p-1)) calculate described interleaving address, capable sequence number is set then increases 1, and judge whether the current line sequence number equals the poor of line number and 1, if, the row sequence number is set increases 1, return step B31, otherwise, step B32 returned.

7, a kind of Turbo code interleaver is characterized in that, described interleaver comprises initialization module, computing module, and, the cache module that control circuit and being used to is stored the buffer of effective interleaving address included, clock signal from the outside is delivered to above-mentioned module respectively, wherein

After initialization module receives initialization enabling signal from the outside, read line number, columns, prime number and the primitive root of bit input matrix from external memory storage according to the weaving length of current business, calculate all row interior exchange basic sequence and storages of current business according to the above-mentioned parameter that reads, to outside output initialization end mark, and comprise the parameter group of weaving length, line number, columns and prime number and be used to read switch mode in the row and exchange the base address of prime number to computing module output;

After computing module receives the enabling signal that external module produces according to the initialization end mark of initialization module output, base address according to current line sequence number and initialization module output, calculating is used to read the switch mode and the address of reading that exchanges prime number in the row of reading that is stored in external memory storage, read switch mode and exchange prime number in the row according to reading the address, and read from the positive backward sign of outside and be stored in the row in the initialization module and exchange basic sequence, according to switch mode in the row that reads, exchange basic sequence in exchange prime number and the row, press the relation of columns and prime number, select following formula to calculate the corresponding interleaving address of the capable i row of j of bit input matrix:

If columns and prime number are equal, then

intterleaver_address = \{\begin{matrix} T (j) * C + s ((i * r_{T (j)}) \mod (p - 1)), [i = 0, . . ., p - 2; j = 0, . . ., R - 1] \\ T (j) * C, [i = p - 1; j = 0, . . ., R - 1] \end{matrix} - - - (1)

If columns equals prime number and 1 sum, then,, then calculate by formula (2) if unequal with the line number and long-pending the comparing of columns of weaving length and bit input matrix, if equate, then calculate by formula (3),

intterleaver_address = \{\begin{matrix} T (j) * C + s ((i * r_{T (j)}) \mod (p - 1)), [i = 0, . . ., p - 2, j = 0, . . ., R - 1] \\ T (j) * C [i = p - 1; j = 0, . . ., R - 1] \\ T (j) * C + p, [i = p; j = 0, . . ., R - 1] \end{matrix} - - - (2)

intterleaver_address = \{\begin{matrix} T (j) * C + p, [i = 0; j = 0, . . ., R - 1] \\ T (j) * C + s ((i * r_{T (j)}) \mod (p - 1)), [i = 0, . . ., p - 2, j = 0, . . ., R - 1] \\ T (j) * C, [i = p - 1; j = 0, . . ., R - 1] \\ T (j) * C + 1, [i = p; j = 0, . . ., R - 1] \end{matrix} - - - (3)

If columns equals the poor of prime number and 1, then

Wherein, T (j) is switch mode in the ranks, and C is the columns of bit input matrix, and R is the line number of bit input matrix, and p is a prime number, s ((i*r _{T (j)}Mod (p-1)) basic sequence for exchanging in the row, r _{T (j)}Be the exchange prime number;

Described computing module exports effective interleaving address sign, the interleaving address that calculates and beginning storage control signal in the cache module control circuit after calculating interleaving address;

Control circuit in the cache module is according to described enabling signal, beginning storage control signal and effective interleaving address sign from the outside, write enable signal to the buffer output that is used to store effective interleaving address, and write address output and read the address to described buffer; The control of the controlled circuit of buffer will write from the effective interleaving address in the interleaving address of computing module output, and requires output buffers in the interleaving address of described buffer according to the sequential of reading of external module.

8, interleaver according to claim 7 is characterized in that, the control circuit in the described cache module is read sequential when inequality what write sequential and external module, stops signal calculated to what computing module output control computing module calculated.

According to claim 7 or 8 described interleavers, it is characterized in that 9, described initialization module comprises parameter extraction module, calculates the memory of the computing unit of exchange basic sequence in the row and the interior exchange of the row basic sequence that storage computation goes out, wherein,

The parameter read module, receive described initialization enabling signal, read described line number, columns, prime number and the primitive root that is stored in bit input matrix in the external memory storage, prime number that output is read and primitive root are exported described base address and described parameter group to computing module to the computing unit that calculates exchange basic sequence in the row;

Calculate the computing unit of exchange basic sequence in the row, exchange basic sequence in all row that calculate described current business according to the prime number and the primitive root of parameter read module output, and export the memory of exchange basic sequence in the row that storage computation goes out to;

The memory of exchange basic sequence in the row that storage computation goes out, receive from computing module read the address time exchange basic sequence in the output current line.

10, interleaver according to claim 9, it is characterized in that, described computing module comprises, first state machine, linage-counter, column counter, address calculation, first multiplier, second multiplier, divider, multiplexer, adder, comparator, output delay unit, control logic, first latch, second latch, the 3rd latch, quad latch and the 5th latch, wherein

Described enabling signal inputs to the Enable Pin of first state machine, and described first state machine is output as linage-counter, column counter, output delay unit and described each latch clock signal is provided respectively, and described clock signal inputs to first state machine;

Described positive backward sign inputs to the control end of linage-counter and column counter respectively, and linage-counter output row sequence number is to address calculation;

Described base address inputs to address calculation, and address calculation calculates the described address of reading that is used to read interior switch mode of row and exchange prime number according to base address and row, and exports this to described external memory storage and read the address;

Input to first multiplier and second multiplier respectively from switch mode in the row of external memory storage output and exchange prime number, first multiplier exports the product of switch mode in line number and the row to first latch, and the output of first latch is connected to the input of comparator; Second multiplier will exchange prime number and export second latch to product from the row sequence number of column counter output, and the output of second latch is connected to the input of divider;

Divider will subtract 1 difference from the output of second latch and prime number and carry out modular arithmetic, export operation result to the 3rd latch, the output of the 3rd latch be connected to exchange basic sequence in the row that described storage computation goes out memory read the address end;

Multiplexer is according to the relation of columns and prime number, select 0 value, prime number, 1 value of inputoutput multiplexer or the row that goes out from storage computation in exchange basic sequence in the row of memory output of exchange basic sequence and carry out multiplexingly, and export to adder;

Adder stack is from the output of multiplexer and from the output of first latch, and output interleaving address to the quad latch, and the output of quad latch is connected to the input of comparator and the input of output delay unit respectively;

Relatively from the interleaving address and the weaving length of quad latch, if interleaving address, is then exported the input of effective interleaving address sign to the five latchs greater than weaving length, the output of the 5th latch is connected to the input of control circuit in the cache module to comparator;

After will delaying time from the interleaving address of quad latch output, the output delay unit exports the buffer in the cache module to;

Control logic receives respectively the output from linage-counter and column counter, according to the input of the control circuit to the cache module of output beginning storage control signal in calculating the sequential of interleaving address.

11, interleaver according to claim 7 is characterized in that, described control circuit comprises, write address counter, read address counter, with the door and second state machine, wherein,

Input to the Enable Pin of second state machine from the described enabling signal of outside, described clock signal inputs to the input of second state machine, the output of second state machine is connected to the input of write address counter and read address counter respectively, and also input to the door input;

Input to input with door from effective interleaving address sign of computing module and beginning storage control signal, be connected to the Enable Pin of writing of buffer with the output of door;

The write address counter write address output is to the write address end of buffer, and read address counter output is read the address and read the address end to buffer.

12, interleaver according to claim 10 is characterized in that, described control circuit comprises, write address counter, read address counter, with door, third state machine, four condition machine and stop the signal calculated generation module, wherein,

Described enabling signal from the outside inputs to the Enable Pin of third state machine and the Enable Pin of four condition machine respectively, described clock signal inputs to the input of third state machine and four condition machine respectively, the output of third state machine be connected to the input of writing counter and with the input of door, the output of four condition machine is connected to the input of read counter;

Input to input with door respectively from effective interleaving address sign of computing module and beginning storage control signal, be connected to the Enable Pin of writing of buffer with the output of door;

The write address counter write address output is to the input of the write address end and the stop signal generation module of buffer, and the input of reading address end and stopping signal calculated generation module of address to buffer read in read address counter output;

Stop the signal calculated generation module the write address write address threshold value that equals to be provided with of input or input read that the address equals to be provided with read address threshold the time, output stops the Enable Pin of signal calculated first state machine to the computing module.