CN1973440A

CN1973440A - LDPC encoder, decoder, system and method

Info

Publication number: CN1973440A
Application number: CNA2005800174426A
Authority: CN
Inventors: 童文; M·贾; P·朱; J·马; C·罗耶
Original assignee: Nortel Networks Ltd
Current assignee: Nortel Networks Ltd; Apple Inc
Priority date: 2004-04-02
Filing date: 2005-04-04
Publication date: 2007-05-30
Also published as: CN1961499B; CN1961499A

Abstract

An LDPC encoder is provided whose complexity increases linearly as a function of block size. They can be implemented with simple logic including a repeater with an irregularly repeating pattern, an interleaver, and an accumulator that performs irregular accumulation.

Description

LDPC encoder, decoder, system and method

技术领域technical field

本发明涉及LDPC编码器、解码器、系统及方法。The present invention relates to LDPC encoder, decoder, system and method.

背景技术Background technique

通过许多研究工作已证明LDPC(低密度奇偶校验)码的性能超过了Turbo码，并且甚至可仅低于香农限0.045dB。这种用于消息传递的算法允许并行计算，并且与Turbo解码算法相比只需很少的存储资源和计算开销。It has been proven by many research works that the performance of LDPC (Low Density Parity Check) codes exceeds that of Turbo codes, and can even be only 0.045dB below Shannon's limit. This algorithm for message passing allows parallel computing and requires very little storage resources and computational overhead compared to the Turbo decoding algorithm.

该消息传递算法是基于线性块编码的奇偶校验矩阵H的特性的，包括：奇偶校验矩阵乘以任何有效码字将得到零向量。校验矩阵的另一重要特性是它是稀疏的，并且矩阵中单元的数目是码字大小的线性函数。因此，解码复杂性是码字的长度的线性函数。The message passing algorithm is based on the properties of the parity check matrix H of the linear block code, including: multiplying the parity check matrix by any valid codeword will result in a zero vector. Another important property of the check matrix is that it is sparse and the number of elements in the matrix is a linear function of the codeword size. Therefore, decoding complexity is a linear function of the length of the codeword.

高效的解码算法的有效性不能保证高效的编码算法的有效性。由线性块编码的理论可知，生成矩阵G通常用来对消息进行编码。生成矩阵G与校验矩阵H的关系为：HG^T＝0mod2。编码的复杂性与编码块按二次方增长。为了对长度为～10³的码字进行编码，运算所需的次数为～10⁶，因而对于实际的应用将是困难的。解决这个问题的一种方法是利用使用线性时间编码的码思想RA-IRA(重复累加-不规则重复累加)。The effectiveness of an efficient decoding algorithm does not guarantee the effectiveness of an efficient encoding algorithm. According to the theory of linear block coding, the generator matrix G is usually used to code the message. The relationship between the generator matrix G and the parity check matrix H is: HG ^T =0mod2. The encoding complexity grows quadratically with encoding blocks. To encode a codeword of length ~ ¹⁰³ , the number of operations required is ~ ¹⁰⁶ , so it will be difficult for practical applications. One way to solve this problem is to exploit the code idea RA-IRA (Repeated Accumulation-Irregular Repeated Accumulation) using linear time encoding.

发明内容Contents of the invention

根据一个广泛的方面，本发明提供了一种适于产生系统输出和奇偶校验输出的具有线性复杂性的LDPC编码器，该编码器包括：重复器，实现不规则的重复码；交织器，对重复器的输出执行交织；累加器，对交织器的输出执行累加并输出奇偶校验输出。According to a broad aspect, the present invention provides an LDPC encoder of linear complexity adapted to generate a system output and a parity output, the encoder comprising: a repeater implementing an irregular repetition code; an interleaver, performing interleaving on the output of the repeater; and an accumulator performing accumulation on the output of the interleaver and outputting a parity output.

在一些实施例中，交织器为S随机或同余交织器。In some embodiments, the interleaver is an S-random or congruential interleaver.

在一些实施例中，累加器执行不规则累加。In some embodiments, the accumulator performs irregular accumulation.

在一些实施例中，累加器执行规则累加。In some embodiments, the accumulator performs regular accumulation.

在一些实施例中，LDPC编码器还含有在重复器和交织器之间的并行到串行的功能。In some embodiments, the LDPC encoder also contains parallel-to-serial functionality between repeaters and interleavers.

在一些实施例中，LDPC编码器通过重复器的重复模式，以及交织器的序列改变来参数化。In some embodiments, the LDPC encoder is parameterized by the repetition pattern of the repeater, and the sequence change of the interleaver.

在一些实施例中，重复模式及序列改变是最佳的。In some embodiments, repeat patterns and sequence changes are optimal.

在一些实施例中，s随机交织器为具有拒绝的半随机算法，向s预交织连续位提供不小于s的后交织距离， $s \leq \sqrt{\frac{N}{2}} .$ In some embodiments, the s random interleaver is a semi-random algorithm with rejection, providing s pre-interleaved consecutive bits with a post-interleaving distance no less than s, $the s \leq \sqrt{\frac{N}{2}} .$

在一些实施例中，LDPC码可由具有双对角线结构的奇偶校验矩阵来表示：In some embodiments, an LDPC code can be represented by a parity check matrix with a double-diagonal structure:

在一些实施例中，整个码以矩阵形式表示如下：In some embodiments, the entire code is expressed in matrix form as follows:

$H h = = [[\begin{matrix} {P P}_{0,0 0,0} & {P P}_{0,1 0,1} & {P P}_{0,2 0,2} & . . . . . . & {P P}_{00,, {m m}_{b b} - - 22} & {P P}_{00,, {m m}_{b b} - - 11} \\ {P P}_{1,0 1,0} & {P P}_{1,1 1,1} & {P P}_{1,2 1,2} & . . . . . . & {P P}_{11,, {m m}_{b b} - - 22} & {P P}_{11,, {m m}_{b b} - - 11} \\ {P P}_{2,0 2,0} & {P P}_{2,1 2,1} & {P P}_{2,2 2,2} & . . . . . . & {p p}_{22,, {m m}_{b b} - - 22} & {P P}_{22,, {m m}_{b b - - 11}} \\ . . & . . & . . & . . . . . . & . . & . . \\ . . & . . & . . & . . . . . . & . . & . . \\ . . & . . & . . & . . . . . . & . . & . . \\ {P P}_{{m m}_{b b} - - 1,0 1,0} & {P P}_{{m m}_{b b} - - 1,1 1,1} & {P P}_{{m m}_{b b} - - 1,2 1,2} & . . . . . . & {P P}_{{m m}_{b b} - - 11,, {m m}_{b b} - - 22} & {p p}_{{m m}_{b b} - - 11,, {m m}_{b b} - - 11} \end{matrix}] = = {P P}^{{H h}_{b b}}$

其中H为大小m×n的矩阵，n为码的长度且m为码中的奇偶校验位的数目，其中P_i，j为一组z×z右移单位矩阵或z×z零矩阵中的一个；矩阵H是由大小为m_b×n_b的二进制基矩阵H_b扩展的，其中n＝z·n_b且m＝z·m_b，并且z为正整数，该基矩阵通过将基矩阵中的每个1用z×z的右移单位矩阵，以及每个0用z×z的零矩阵代替来扩展；将H_b分成两部分，其中H_b1与系统位对应，且H_b2与奇偶校验位对应；又将H_b2分成两部分，其中向量h_b具有奇权重，且H′_b2具有其i行j列的矩阵元素在i＝j，i＝j+1时等于1，其余为0的双对角线结构：where H is a matrix of size m×n, n is the length of the code and m is the number of parity bits in the code, where _Pi,j is a set of z×z right-shifted identity matrices or z×z zero matrices One of; the matrix H is extended by the binary base matrix H _b of size m _b ×n _b , where n=z·n _b and m=z·m _b , and z is a positive integer, the base matrix is obtained by adding the base Each 1 in the matrix is extended by a z×z right-shifted identity matrix, and each 0 is replaced by a z×z zero matrix; divide H _b into two parts, where H _b1 corresponds to the systematic bit, and H _b2 corresponds to The parity bit corresponds; H _b2 is divided into two parts, wherein the vector h _b has an odd weight, and H' _b2 has its i row and j column matrix elements equal to 1 when i=j, i=j+1, and the rest Double diagonal structure with 0:

其中h_b(0)＝1，h_b(m-1)＝1，且第三值h_b(j)等于1，0＜j＜(m_b-1)。Where h _b (0)=1, h _b (m−1)=1, and the third value h _b (j) is equal to 1, 0<j<(m _b −1).

在一些实施例中，LDPC编码器还适于允许基于具有速率兼容校验节点处理器构造特征的普通编码器/解码器对一组不同码率的构造以及对与校验节点级联相匹配的基于压缩的速率的构造。In some embodiments, the LDPC encoder is also adapted to allow the construction of a set of different code rates based on a common encoder/decoder with rate-compatible check node processor construction features and a matching check node concatenation. Construct based on compression rate.

根据另一广范的方面，本发明提供了一种具有基矩阵结构的LDPC编码器，它避免了在扩展的矩阵中具有多个权重为1的列。According to another broad aspect, the present invention provides an LDPC encoder with a base matrix structure that avoids having multiple columns with a weight of 1 in the extended matrix.

根据另一广范的方面，本发明提供了一种LDPC编码器，实现了可由具有如下双对角线结构的奇偶校验矩阵来表示的LDPC码：According to another broad aspect, the present invention provides an LDPC encoder implementing an LDPC code that can be represented by a parity check matrix having the following bi-diagonal structure:

$H h = = [\begin{matrix} {P P}_{0,0 0,0} & {P P}_{0,1 0,1} & {P P}_{0,2 0,2} & . . . . . . & {P P}_{00,, {n no}_{b b} - - 22} & {P P}_{00,, {n no}_{b b} - - 11} \\ {P P}_{1,0 1,0} & {P P}_{1,1 1,1} & {P P}_{1,2 1,2} & . . . . . . & {P P}_{11,, {n no}_{b b} - - 22} & {P P}_{11,, {n no}_{b b} - - 11} \\ {P P}_{2,0 2,0} & {P P}_{2,1 2,1} & {P P}_{2,2 2,2} & . . . . . . & {P P}_{22,, {n no}_{b b} - - 22} & {P P}_{22,, {n no}_{b b} - - 11} \\ . . & . . & . . & . . & . . \\ . . & . . & . . & . . . . . . & . . & . . \\ . . & . . & . . & . . & . . \\ {P P}_{{m m}_{b b} - - 1,0 1,0} & {P P}_{{m m}_{b b} - - 1,1 1,1} & {P P}_{{m m}_{b b} - - 1,2 1,2} & . . . . . . & {P P}_{{m m}_{b b} - - 11,, {n no}_{b b} - - 22} & {P P}_{{m m}_{b b} - - 11,, {n no}_{b b} - - 11} \end{matrix}] = = {P P}^{{H h}_{b b}}$

根据另一广范的方面，本发明提供一种给定信息序列s，执行LDPC编码以确定奇偶校验序列P的方法，它含有以下步骤：将信息序列s分成z位的k_b＝n_b-m_b组，使该分组s被表示为u，According to another broad aspect, the present invention provides a method of performing LDPC coding to determine a parity sequence P given an information sequence s, comprising the steps of: dividing the information sequence s into k _b = n _b of z bits -m _bgroup , causes the group s to be denoted as u,

u＝[u(0)u(1)…u(k_b-1)]，u=[u(0)u(1)...u(k _b -1)],

其中u的每个元素是如下的列向量where each element of u is a column vector as follows

u(i)＝[s_izs_iz+1…s_(i+1)z-1]^T u(i)＝[s _iz s _iz+1 …s _(i+1)z-1 ] ^T

使用模型矩阵H_b，在z的组中确定奇偶校验序列p-令分组的奇偶校验序列p用v表示，Using the model matrix _Hb , determine the parity sequence p in the group of z—let the parity sequence p of the group be denoted by v,

v＝[v(0)v(1)…v(m_b-1)]v=[v(0)v(1)...v(m _b -1)]

其中v的每个元素为如下的列向量where each element of v is the following column vector

v(i)＝[p_izp_iz+1…p_(i+1)z-1]^T v(i)＝[p _iz p _iz+1 …p _(i+1)z-1 ] ^T

执行初始化步骤以确定v(0)；perform an initialization step to determine v(0);

执行递归以根据v(i)确定v(i+1)，0≤i≤m_b-2；Perform recursion to determine v(i+1) from v(i), 0≤i≤m _b -2;

在一些实施例中，v(0)的表达式可通过对H_b的行求和得到以获得In some embodiments, the expression for v(0) can be obtained by summing the rows of H _b to obtain

${P P}_{P P ((x x,, {k k}_{b b}))} v v ((00)) = = {Σ Σ}_{j j = = 00}^{{k k}_{b b} - - 11} {Σ Σ}_{i i = = 00}^{{m m}_{b b} - - 11} {P P}_{p p ((i i,, j j))} u u ((j j)) - - - - - - ((11))$

其中x为其条目为非负且不成对的h_b的行索引，1≤x ≤m_b-2，，且p_i表示按大小i的循环右移z×z单位矩阵。方程(1)通过乘P_p(x，kb) ^-1求解v(0)，且 $P_{P (x, k_{b})}^{- 1} = p_{z - p (x, k_{b})},$ 因为p(x，k_b)表示循环移位。where x is the row index of h _b whose entries are non-negative and unpaired, 1 ≤ x ≤ m _b -2, and p _i represents a z×z identity matrix shifted right by a cycle of size i. Equation (1) solves for v(0) by multiplying P _p(x,kb) ^-1 , and $P_{P (x, k_{b})}^{- 1} = p_{z - p (x, k_{b})},$ Because p(x, k _b ) represents a cyclic shift.

在一些实施例中，递归根据下式规定：In some embodiments, recursion is specified according to the following equation:

$v v ((11)) = = {Σ Σ}_{j j = = 00}^{{k k}_{b b} - - 11} {P P}_{P P ((i i,, j j))} u u ((j j)) + + {P P}_{P P ((i i,, {k k}_{b b}))} v v ((00)),, i i = = 00,, - - - - - - ((22))$

$v v ((i i + + 11)) = = v v ((i i)) + + {Σ Σ}_{j j = = 00}^{{k k}_{b b} - - 11} {P P}_{p p ((i i,, j j))} u u ((j j)) + + {P P}_{p p ((i i,, {k k}_{b b}))} v v ((00)),, i i = = 11,, . . . . . .,, {m m}_{b b} - - 22 - - - - - - ((33))$

其中in

P_-1≡0_z×z P _-1 ≡ 0 _z×z

在一些实施例中，LDPC编码器含有：并行节点处理结构，适宜于任何选择的码率和交织器选择，用于对根据任何一种如上所述的方法实现的码进行解码。In some embodiments, the LDPC encoder comprises: a parallel node processing structure, adapted to any selected code rate and interleaver selection, for decoding codes implemented according to any one of the methods described above.

附图说明Description of drawings

图1是RA码结构的示意图；Fig. 1 is the schematic diagram of RA code structure;

图2是RA编码器结构的示意图；Fig. 2 is the schematic diagram of RA coder structure;

图3是解码算法的示意图；Fig. 3 is a schematic diagram of a decoding algorithm;

图4是该解码器的改进交织器的示意图；Fig. 4 is the schematic diagram of the improved interleaver of this decoder;

图5是消息计算的示意图；Fig. 5 is a schematic diagram of message calculation;

图6是校验节点计算的示意图；Fig. 6 is a schematic diagram of check node calculation;

图7是事件的完全组的示意图；Figure 7 is a schematic diagram of a complete set of events;

图8是函数ln((exp(x)-1)/(exp(x)+1))的曲线图；Fig. 8 is a graph of the function ln((exp(x)-1)/(exp(x)+1));

图9是不规则变量节点的重复表的图形；Figure 9 is a graphic representation of a repeat table of irregular variable nodes;

图10是BER对Eb/No的曲线图；Figure 10 is a graph of BER versus Eb/No;

图11是BER对Eb/No可变速率解码器结构的曲线图；Fig. 11 is the graph of BER to Eb/No variable rate decoder structure;

图12是可变速率解码器的结构示意图；Fig. 12 is a schematic structural diagram of a variable rate decoder;

图13是在校验节点处的系统消息的数目的曲线图；Figure 13 is a graph of the number of system messages at a check node;

图14是“可变速率解码器的误帧率：IRA-7与3GPP turbo，帧大小为1000位”的曲线图；Figure 14 is a graph of "Frame error rate of variable rate decoder: IRA-7 and 3GPP turbo, frame size is 1000 bits";

图15是基本的IRA解码器结构的示意图；Figure 15 is a schematic diagram of a basic IRA decoder structure;

图16是并行节点处理的示意图；Fig. 16 is a schematic diagram of parallel node processing;

图17是交织器中的重复因子的示意图；Figure 17 is a schematic diagram of a repetition factor in an interleaver;

图18是交织器结构的示意图；Figure 18 is a schematic diagram of an interleaver structure;

图19是偶-奇交织器的示意图；Figure 19 is a schematic diagram of an even-odd interleaver;

图20是扩展的奇-偶交织器的示意图；Figure 20 is a schematic diagram of an extended odd-even interleaver;

图21是基本的校验节点处理器的示意图；Figure 21 is a schematic diagram of a basic check node processor;

图22是1/2速率的校验节点处理器的示意图；FIG. 22 is a schematic diagram of a 1/2 rate check node processor;

图23是1/2速率变量的校验节点处理器的示意图；FIG. 23 is a schematic diagram of a check node processor for a 1/2 rate variant;

图24是速率兼容校验节点处理器1/4、1/3、1/2的示意图；FIG. 24 is a schematic diagram of rate-compatible check node processors 1/4, 1/3, and 1/2;

图25是速率组构造的示意图；Figure 25 is a schematic diagram of a rate group structure;

图26是校验节点处理器2/3的示意图；FIG. 26 is a schematic diagram of a check node processor 2/3;

图27是校验节点处理器4/5的示意图；FIG. 27 is a schematic diagram of a check node processor 4/5;

图28是不带符号确定的节点处理器基结构(变量及校验)的示意图；Fig. 28 is a schematic diagram of a node processor base structure (variables and checks) without sign determination;

图29是除奇偶校验符号外的完整的校验节点处理器结构2+2LUT示意图；FIG. 29 is a schematic diagram of a complete check node processor structure 2+2LUT except parity symbols;

图30是奇偶校验节点的初始化的示意图；FIG. 30 is a schematic diagram of initialization of a parity check node;

图31是通过奇偶校验变量节点处理器进行处理的示意图(无需计算)；Figure 31 is a schematic diagram of processing by a parity variable node processor (no computation required);

图32是具有哑符号压缩的级联的校验节点处理器的示意图；32 is a schematic diagram of cascaded check node processors with dummy symbol compression;

图33是变量节点处理器3的示意图；FIG. 33 is a schematic diagram of a variable node processor 3;

图34是变量节点处理器3-3-3-5的示意图；Figure 34 is a schematic diagram of a variable node processor 3-3-3-5;

图35是变量节点处理器7的示意图；FIG. 35 is a schematic diagram of a variable node processor 7;

图36是IRA-7与3GPP2 turbo码的比较FER的曲线图；Figure 36 is a graph of the comparative FER of IRA-7 and 3GPP2 turbo codes;

图37是IRA-7与3GPP2 turbo码的比较BER的曲线图；Figure 37 is a graph of the comparative BER of IRA-7 and 3GPP2 turbo codes;

图38是简单压缩损失FER的曲线图；Figure 38 is a graph of simple compression loss FER;

图39是简单压缩损失BER的曲线图；Figure 39 is a graph of simple compression loss BER;

图40是重复累加码FER的曲线图；Figure 40 is a graph of repeated accumulation code FER;

图41是重复累加码BER的曲线图；Figure 41 is a graph of the repeated accumulation code BER;

图42是重复因子减少的FER曲线图；Figure 42 is a FER graph of reduction in repetition factor;

图43是按RA-3码简单压缩的FER曲线图；Fig. 43 is the FER curve diagram of simple compression by RA-3 code;

图44是根据迭代次数的性能的FER曲线图；以及Figure 44 is a FER graph of performance according to the number of iterations; and

图45是根据迭代次数的性能的BER曲线图。Fig. 45 is a graph of BER of performance according to the number of iterations.

具体实施方式Detailed ways

图1示出了对称RA码结构的示例，其中编码的复杂性随着码块的长度线性地增长。图示的示例取4个系统位并且产生5个校验位。这4个系统位输入图示在10、12、14、16处。每个系统位的多个拷贝被输入到交织器18。经选择的交织器输出被馈送到产生奇偶校验位的5个校验节点18、20、22、24、26。LDPC消息传递算法适用于这种码的结构。换句话说这种码允许通过Tanner图来进行解码。实际得到的性能不比LDPC类的其他码差。Figure 1 shows an example of a symmetric RA code structure, where the coding complexity grows linearly with the code block length. The illustrated example takes 4 systematic bits and produces 5 parity bits. The 4 system bit inputs are shown at 10,12,14,16. Multiple copies of each systematic bit are input to the interleaver 18 . The selected interleaver output is fed to 5 check nodes 18, 20, 22, 24, 26 which generate parity bits. The LDPC message passing algorithm is suitable for this code structure. In other words, this code allows decoding through Tanner graphs. The actual performance obtained is no worse than other codes of the LDPC class.

在图2中以框图的形式示出由本发明的实施例提供的编码器。该编码器具有用于接收将被编码的系统位的输入50。编码器输出含有系统位68及奇偶校验位66。系统位输入50被输入到重复器52，它产生馈送到并串变换器54的并行输出53。串行输出55被输入到交织器56。交织器输出57被输入到累加器。在该说明性示例中累加器含有“异或”功能60及状态元件62，但其他设计也是可能的。“异或”功能60的输出通过状态元件被反馈到“异或”功能60的第二输入端。不时地，最好在不规则累加周期内，在累加器58(说明性示例中的“异或”功能60)的输出端的位被当作奇偶校验位66的其中之一。它用开关64示意性地说明。奇偶校验位在“异或”功能60的输出处取的次数是编码器结构的函数。An encoder provided by an embodiment of the present invention is shown in block diagram form in FIG. 2 . The encoder has an input 50 for receiving the systematic bits to be encoded. The encoder output contains systematic bits 68 and parity bits 66 . The systematic bit input 50 is input to a repeater 52 which produces a parallel output 53 which is fed to a parallel to serial converter 54 . The serial output 55 is input to an interleaver 56 . The interleaver output 57 is input to an accumulator. In this illustrative example the accumulator contains an "exclusive OR" function 60 and a state element 62, but other designs are possible. The output of the "exclusive OR" function 60 is fed back to a second input of the "exclusive OR" function 60 via a state element. From time to time, preferably during irregular accumulation cycles, a bit at the output of accumulator 58 (exclusive OR function 60 in the illustrative example) is treated as one of parity bits 66 . It is schematically illustrated with switch 64 . The number of times the parity bit is taken at the output of the XOR function 60 is a function of the encoder structure.

为了增强纠错能力，最好系统符号的不规则重复，与交织器之后的不规则求和一样可被使用。因此，以下三个表格可被用来对图2的结构中的码进行设置：To enhance the error correction capability, preferably irregular repetition of systematic symbols, as well as irregular summation after the interleaver, can be used. Therefore, the following three tables can be used to set the codes in the structure of Figure 2:

1、系统部分重复的表格；1. Partially repeated tables in the system;

2、交织器；2. Interleaver;

3、在交织之后的求和表格；3. The sum table after interleaving;

含有系统部分重复及求和信息两者的表格的示例在下文示出。重复表格列识别重复器输出如何根据系统位输入产生。在说明性示例中，存在8位的系统输入。该重复列指示除了该位被重复之外，有多少次被重复，并且求和表格列指示交织器的输出有多少位被求和以产生各奇偶校验位输出。求和表格将在图2的示例的输出“异或”功能60处控制奇偶校验位66的产生。在说明性示例中，存在为每8个系统位而产生的总计5个奇偶校验位。An example of a table containing both systematic partial repetition and summation information is shown below. The repeat table column identifies how the repeater output is generated from the system bit input. In the illustrative example, there are 8 bits of system input. The repeat column indicates how many times the bit is repeated, and the summation table column indicates how many bits of the interleaver's output are summed to produce each parity bit output. The summation table will control the generation of parity bits 66 at the output XOR function 60 of the example of FIG. 2 . In the illustrative example, there are a total of 5 parity bits generated for every 8 systematic bits.

我们具有8位的系统位，我们为8位使用左列循环重复以便扩展为：We have 8 bits of system bits, we use the left column for 8 bits to cyclically repeat to expand to:

11222333＝17位11222333 = 17 digits

这些位被交织并且然后右列的求和表格被用来求和以产生奇偶校验位：The bits are interleaved and then the summation table in the right column is used to sum to produce the parity bits:

3→1 4→1 5→1 3→1 2→1我们有总计5个奇偶校验位此示例的码率为8/(8+5)＝8/133→1 4→1 5→1 3→1 2→1 We have a total of 5 parity bits The code rate for this example is 8/(8+5)=8/13

表格1编码表格(一个示例)Form 1 Encoding form (an example)

重复表格 repeat form 求和表格 summation form 0 0 3 3 0 0 4 4 1 1 5 5 1 1 3 3 1 1 2 2 2 2 2 2 2 2

由上表格可见，第一位及第二位被包含一次，第三、第四和第五位被包含两次，并且第六、第七及第八位被包括三次。由上表格可见，为了获得第一校验位，“异或”运算必须在交织器输出端按3位顺序地执行。下一个校验位通过“异或”操作用交织器输出的下4个位及第一个校验位等，使用在表格中指定的这样的位的数目来获得。用来指示每个系统位被重复多少次的表格的使用是可用来实现这个功能的结构的简单示例。教程中(course)的每个位的重复的次数会是具体的码设计的函数，如使用的系统位的数目，即块大小。类似地，产生的奇偶校验位会是具体码设计的函数，并且用来产生各自奇偶校验位的交织器的输出位的数目是码特定的参数。表格1中编码表格给出的示例仅为极特定的示例。As can be seen from the above table, the first and second digits are included once, the third, fourth and fifth digits are included twice, and the sixth, seventh and eighth digits are included three times. It can be seen from the above table that in order to obtain the first parity bit, the "exclusive OR" operation must be performed sequentially on 3 bits at the output of the interleaver. The next parity bit is obtained by XORing the next 4 bits output by the interleaver and the first parity bit, etc., using the number of such bits specified in the table. The use of a table to indicate how many times each systematic bit is repeated is a simple example of a structure that can be used to accomplish this. The number of repetitions of each bit in the course (course) will be a function of the specific code design, such as the number of system bits used, that is, the block size. Similarly, the parity bits generated will be a function of the particular code design, and the number of output bits of the interleaver used to generate the respective parity bits is a code-specific parameter. The examples given in the coding tables in Table 1 are very specific examples only.

在示例中，图9示出了不规则重复因子并且基于不同的码率，在表格4中列出了求和因子。In an example, Fig. 9 shows irregular repetition factors and summation factors are listed in Table 4 based on different code rates.

在优选实施例中，交织器为“s随机”交织器。所选择的算法为具有拒绝的半随机算法，向s预交织连续位提供不小于s的后交织距离。如已经证明的，如果 $s \leq \sqrt{\frac{N}{2}},$ 则这样的交织过程收敛。这种交织的方法在得到的矩阵中允许排除短周期。In a preferred embodiment, the interleaver is an "s-random" interleaver. The selected algorithm is a semi-random algorithm with rejection, providing s pre-interleaved consecutive bits with a post-interleaving distance not less than s. As has been proven, if $the s \leq \sqrt{\frac{N}{2}},$ Then such an interleaving process converges. This method of interleaving allows the exclusion of short periods in the resulting matrix.

直接编码direct encoding

通常，每个LDPC码都是系统的线性块码。在该组LDPC码中的每个LDPC码由大小m×n的矩阵H来规定，其中n为码的长度且m为码中奇偶校验位的数目。系统位的数目为k＝n-m。In general, each LDPC code is a systematic linear block code. Each LDPC code in the set of LDPC codes is specified by a matrix H of size mxn, where n is the length of the code and m is the number of parity bits in the code. The number of systematic bits is k=n-m.

矩阵H被定义为基矩阵的扩展并可表示为：The matrix H is defined as an extension of the basis matrix and can be expressed as:

$H h = = [\begin{matrix} {P P}_{0,0 0,0} & {P P}_{0,1 0,1} & {P P}_{0,2 0,2} & . . . . . . & {P P}_{00,, {n no}_{b b} - - 22} & {P P}_{00,, {n no}_{b b} - - 11} \\ {P P}_{1,0 1,0} & {P P}_{1,1 1,1} & {P P}_{1,2 1,2} & . . . . . . & {P P}_{11,, {n no}_{b b} - - 22} & {P P}_{11,, {n no}_{b b} - - 11} \\ {P P}_{2,0 2,0} & {P P}_{2,1 2,1} & {P P}_{2,2 2,2} & . . . . . . & {P P}_{22,, {n no}_{b b} - - 22} & {P P}_{22,, {n no}_{b b} - - 11} \\ . . & . . & . . & . . & . . \\ . . & . . & . . & . . . . . . & . . & . . \\ . . & . . & . . & . . & . . \\ {P P}_{{m m}_{b b} - - 1,0 1,0} & {P P}_{{m m}_{b b} - - 1,1 1,1} & {P P}_{{m m}_{b b} - - 1,2 1,2} & . . . . . . & {P P}_{{m m}_{b b} - - 1, 1, {n no}_{b b} - - 22} & {P P}_{{m m}_{b b} - - 11,, {n no}_{b b} - - 11} \end{matrix}] = = {P P}^{{H h}_{b b}}$

其中P_l，j是一组z×z右移单位矩阵或z×z零矩阵之一。矩阵H由大小m_b×n_b的二进制基矩阵H_b扩展，其中n＝z·n_b且m＝z·m_b，并且z为正整数。该基矩阵通过将基矩阵中的每个1用z×z右移单位矩阵，且每个0用z×z的零矩阵代替来扩展。因此这个设计通过改变子矩阵的大小z来适应不同的包大小。where P _l,j is one of a set of z×z right-shifted identity matrices or z×z zero matrices. The matrix H is extended by a binary basis matrix H _b of size m _b ×n _b , where n=z·n _b and m=z· _mb , and z is a positive integer. The basis matrix is expanded by right-shifting each 1 in the basis matrix by the identity matrix by z×z, and replacing each 0 with a z×z zero matrix. Therefore this design adapts to different packet sizes by changing the size z of the sub-matrix.

已知这样的H_b可分为两部分，其中H_b1与系统位对应，且H_b2与奇偶校验位对应。It is known that such H _b can be divided into two parts, where H _b1 corresponds to systematic bits, and H _b2 corresponds to parity bits.

根据本发明的一方面，H_b2部分又被分为两部分，其中其中h_b具有奇权重，且H′_b2具有在i行j列处的矩阵元素在i＝j，i＝j+1时等于1，其余为0的双对角线结构：According to an aspect of the invention, part H _b2 is further divided into two parts, where h _b has odd weights, and H' _b2 has matrix elements at row i and column j at i=j, i=j+1 Double diagonal structure equal to 1 and the rest 0:

该基矩阵有h_b(0)＝1，h_b(m-1)＝1，且第三值h_b(j)，0＜j＜(m_b-1)等于1。基矩阵的结构避免在扩展的矩阵中有多个权重为1的列，这可通过交织器的优化来实现。The base matrix has h _b (0)=1, h _b (m−1)=1, and the third value h _b (j), 0<j<(m _b −1) is equal to 1. The structure of the base matrix avoids having multiple columns with a weight of 1 in the expanded matrix, which can be achieved through the optimization of the interleaver.

更具体地说，非零子矩阵由具体的循环移位值来循环右移。H′_b2中的每个1分配了0的移位大小，并且当扩展为H时用z×z单位矩阵来代替。这允许了具有简单的递归电路的双对角线结构的实现。位于h_b的顶部和底部的两个1分配了相等的移位大小，并且对h_b中间的第三个1给定了不成对的移位大小。该不成对的移位大小为0。More specifically, the non-zero submatrix is cyclically shifted right by the specified cyclic shift value. Each 1 in _H'b2 is assigned a shift size of 0, and is replaced by a z×z identity matrix when expanded to H. This allows the realization of double-diagonal structures with simple recursive circuits. The two 1s at the top and bottom of _hb are assigned equal shift sizes, and the third 1 in the middle of _hb is given an unpaired shift size. The unpaired shift size is 0.

编码是给出信息序列s确定奇偶校验序列p的过程。为进行编码，信息块s被分成z位的k_b＝n_b-m_b组。令该组s用u表示，Encoding is the process of determining the parity sequence p given the information sequence s. For encoding, the information block s is divided into k _b =n _b -m _b groups of z bits. Let the group s be denoted by u,

u＝[u(0)u(1)…u(k_b-1)]，u=[u(0)u(1)...u(k _b -1)],

其中u的每个元素为如下的列向量：where each element of u is a column vector as follows:

u(i)＝[s_izs_iz+1…s_(i+1)z＝1]^T u(i)=[s _iz s _iz+1 ... s _(i+1)z=1 ] ^T

使用模型矩阵H_b，奇偶校验序列p在z的组中确定。令该组奇偶校验序列p用v表示，Using the model matrix H _b , the parity sequence p is determined in the group of z. Let the set of parity check sequences p be denoted by v,

v＝[v(0)v(1)…v(m_b-1)]，v=[v(0)v(1)...v(m _b -1)],

其中v的每个元素为如下的列向量：where each element of v is the following column vector:

v(i)＝[p_izp_iz+1…p_(i+1)z+1]^T v(i)＝[p _iz p _iz+1 …p _(i+1)z+1 ] ^T

编码分两个步骤进行，(a)初始化，其中确定v(O)，以及(b)递归，其中根据v(i)确定v(i+1)，0≤i≤m_b-2。The encoding is performed in two steps, (a) initialization, where v(0) is determined, and (b) recursion, where v(i+1) is determined from v(i), 0≤i≤m _b -2.

v(0)的表格达式通过对H_b的行进行求和得到以便获得：The table expression for v(0) is obtained by summing the rows of H _b to obtain:

${P P}_{p p (({x x}_{11} {k k}_{b b}))} v v ((00)) = = {Σ Σ}_{j j = = 00}^{{k k}_{b b} - - 11} {Σ Σ}_{i i = = 00}^{{m m}_{b b} - - 11} {P P}_{p p ((11,, j j))} u u ((j j)) - - - - - - ((11))$

其中x是h_b的行系数，1≤x≤m_b-2，其中条目为非负且不成对的，并且p_i表示按大小i循环右移的z×z单位矩阵。方程(1)通过乘P_p(x，kb) ^-1来求解v(0)，并且 $P_{p (x, k_{b})}^{- 1} = P_{z - p (x, k_{b}),}$ 因为p(x，k_b)表示循环移位。where x is the row coefficient of h _b , 1 ≤ x ≤ m _b −2, where entries are non-negative and unpaired, and p _i represents the z × z identity matrix cyclically shifted right by size i. Equation (1) is solved for v(0) by multiplying P _p(x,kb) ^-1 , and $P_{p (x, k_{b})}^{- 1} = P_{z - p (x, k_{b}),}$ Because p(x, k _b ) represents a cyclic shift.

考虑H′_b2的结构，递归可如下得到，Considering the structure of H′ _b2 , the recursion can be obtained as follows,

$v v ((11)) = = {Σ Σ}_{j j = = 00}^{{k k}_{b b} - - 11} {P P}_{p p ((11,, j j))} u u ((j j)) + + {P P}_{p p ((11,, {k k}_{b b}))} v v ((00)),, i i = = 00,, - - - - - - ((22))$

$v v ((i i + + 11)) = = v v ((i i)) + + {Σ Σ}_{j j = = 00}^{{k k}_{b b} - - 11} {P P}_{p p ((11,, j j))} u u ((j j)) + + {P P}_{p p ((11,, {k k}_{b b}))} v v ((00)),, i i = = 11,, . . . . . .,, {m m}_{b b} - - 22 - - - - - - ((33))$

其中in

P_-1≡0_z×s。P ₋₁ ≡0 _z×s .

因此不在v(0)中的所有奇偶校验位通过对方程(2)在0≤i≤m_b-2时进行估计来确定。All parity bits not in v(0) are therefore determined by estimating equation (2) for 0≤i≤mb _- 2.

方程(1)和(2)完整地描述了编码算法。这些方程也具有按照标准数字逻辑体系结构的直接解译。更具体地说，它们能易于使用参考上面图2描述的编码体系结构来实现。Equations (1) and (2) completely describe the encoding algorithm. These equations also have a straightforward interpretation according to standard digital logic architectures. More specifically, they can be readily implemented using the encoding architecture described with reference to Figure 2 above.

基本解码器结构Basic Decoder Structure

解码算法的如下改进是可能的：The following improvements to the decoding algorithm are possible:

1、最小和(Min-sum)算法(最大Log MAP的模拟)1. Min-sum algorithm (simulation of maximum Log MAP)

2、和积(sum-product)(Log-MAP的模拟)2. Sum-product (simulation of Log-MAP)

a、E展示(E-presentation)中的和积a. Sum product in E-presentation

b、概率解码(tanh()规则)。b. Probabilistic decoding (tanh() rule).

用公知的图形解码概念，解码被反复地执行，即迭代的目的是将奇偶校验信息供给下一次迭代。因此，对最接近的合法码字的搜索由连续逼近方法来执行。已显示这种方法的结果接近最大似然判决。With the well known concept of graphic decoding, the decoding is performed iteratively, ie the purpose of the iterations is to feed the parity information to the next iteration. Therefore, the search for the closest legal codeword is performed by a sequential approximation method. The results of this method have been shown to be close to maximum likelihood decisions.

图3示出了消息传递算法框图的示例。每个图的边沿匹配两个被称为消息的数：从变量节点到校验节点的消息，以及从校验节点到变量节点的消息。每个消息是像软判决的数。在进行解码之前它们被初始化到零。消息阵列的大小等于解码器的内部交织器的大小并且交织器用来对它们进行序列改变。Figure 3 shows an example of a message passing algorithm block diagram. Each graph edge matches two numbers called messages: messages from variable nodes to check nodes, and messages from check nodes to variable nodes. Each message is like a number of soft verdicts. They are initialized to zero before decoding. The size of the message array is equal to the size of the internal interleaver of the decoder and the interleaver is used to permutate them.

对于RA码，解码器的内部交织器根据编码器的内部交织器按照包含在交织过程中的奇偶校验位来进行区分。参见图4。For RA codes, the inner interleaver of the decoder differentiates from the inner interleaver of the encoder by the parity bits included in the interleaving process. See Figure 4.

重复及求和的表格根据交织器而变化。当进行解码时，系统节点及奇偶校验节点并不区分，而是两者都被视作变量节点。The table for repetition and summation varies according to the interleaver. When decoding, system nodes and parity nodes are not distinguished, but both are considered as variable nodes.

计算从变量节点到校验节点的输出消息的运算包括对变量节点从其他校验节点接收的所有消息求和，除了假定接收该消息的一个之外，加上从解调器接收的软判决。参见图5。The operation to compute the output message from the variable node to the check node consists of summing all the messages received by the variable node from other check nodes, except the one that was supposed to receive the message, plus the soft decision received from the demodulator. See Figure 5.

在从校验节点到变量节点的输出消息的计算期间，为期输出消息被计算的来自变量节点的输入消息被忽略。During computation of output messages from check nodes to variable nodes, input messages from variable nodes for which output messages are computed are ignored.

从校验节点到变量节点的消息计算的运算有两部分：There are two parts to the calculation of the message calculation from the check node to the variable node:

●消息符号的规定，以及● provisions for message symbols, and

●消息的模的规定。●The regulation of the mode of the message.

消息的符号由校验和的零相等条件来规定。因此，计算了来自变量节点的输入消息的和，并且得到的符号被分配给输出消息。计算来自校验节点的输出消息的简单方法(最小和)。The sign of the message is specified by the zero equality condition of the checksum. Thus, the sum of the input messages from the variable nodes is calculated and the resulting sign is assigned to the output message. Simple method (minimum sum) for computing output messages from check nodes.

输出消息模由图5中的函数来计算。该函数为判决函数或对数似然比。函数f具有可交换的特征：The output message modulo is computed by the function in Figure 5. This function is a decision function or a log-likelihood ratio. The function f has commutative characteristics:

f(a，b，c，d)＝f(a，f(b，f(c，f(d))))f(a,b,c,d)=f(a,f(b,f(c,f(d))))

f(d)＝df(d)=d

存在几种设置函数f的方法：There exist several ways to set the function f:

1.最简单的方法是通常所说的最小和算法。输出消息的绝对值1. The simplest method is the so-called minimum sum algorithm. Absolute value of the output message

等于所考虑的输入消息的最小模：is equal to the smallest modulus of the input message under consideration:

f(|Q_m′n|，except_|Q_m′n′|)＝min_m′n′(|Q_m′n|)f(|Q _m′n |, except_|Q _m′n′ |)=min _m′n′ (|Q _m′n |)

1.另一方法类似于LOG MAP算法中的函数E的计算。该函数f由下式给出：1. Another method is similar to the calculation of the function E in the LOG MAP algorithm. The function f is given by:

f(a，b)＝mmin(a，b)+δ，f(a,b)=mmin(a,b)+δ,

δ＝log(1-exp(-|a+b|))-log(1-exp(-|a-b|))δ=log(1-exp(-|a+b|))-log(1-exp(-|a-b|))

函数E(x)＝log(1-exp(-|x|))，广泛用在turbo编码中，可设置为表格。The function E(x)=log(1-exp(-|x|)), which is widely used in turbo coding, can be set as a table.

1.方法2有一种改进，其中：1. Method 2 has an improvement, where:

$δ δ = = \{\begin{matrix} 11,, | | a a - - b b | | \leq \leq 11,, | | a a + + b b | | > > 11 \\ - - 11,, | | a a - - b b | | > > 11,, | | a a + + b b | | \leq \leq 11 \\ 00,, else else \end{matrix}\}$

该方法不需要函数E表格。然而，此方法导致性能的降低。This method does not require a function E form. However, this approach results in reduced performance.

由于来自带有即时符号考虑的校验节点消息计算，方法2的运算的次数可减少。以下描述实现这个的该技术。The number of operations of Method 2 can be reduced due to message calculations from check nodes with immediate symbol considerations. The technique to achieve this is described below.

E展示中的校验节点的对数似然比算法计算Calculation of the log likelihood ratio algorithm of the check node in E display

考虑函数f可交换的特征，让我们考虑基本的“箱求和”(“box-sum”)运算或对数似然比的计算。Considering the commutative character of the function f, let us consider the basic "box-sum" ("box-sum") operation or computation of the log-likelihood ratio.

$λ λ = = ln ln ((\frac{{P P}_{i i = = 11}}{{P P}_{i i = = p p}})) = = ln ln ((\frac{P P}{11 - - P P})) = = \frac{22 x x}{{σ σ}^{22}}' ' \begin{matrix} {p p}_{i i = = 11} = = p p \\ {p p}_{i i = = v v} = = 11 - - p p \end{matrix} - - - - - - ((11))$

其中p为传送1的后验概率，在接收的信号等于x的条件下，信号为BPSK：+1，-1；并且噪声为具有离差σ²的AWGN。where p is the posterior probability of transmitting 1, under the condition that the received signal is equal to x, the signal is BPSK: +1, -1; and the noise is AWGN with dispersion σ ² .

分别地，λ为判决函数或对数似然比对数。λ is the decision function or log-likelihood ratio logarithm, respectively.

$e^{λ} = \frac{P}{1 - p}'$ (1-p)c^λ＝p′ $P = \frac{e^{λ}}{1 + e^{λ}}'$ $1 - P = \frac{1}{e^{λ} + 1}$ $e^{λ} = \frac{P}{1 - p}'$ (1-p)c ^λ = p' $P = \frac{e^{λ}}{1 + e^{λ}}'$ $1 - P = \frac{1}{e^{λ} + 1}$

问题陈述：如果后验概率p₁及p₂(对数似然比对数λ₁，λ₂)是已知的，则图6中的后验概率p₃(对数似然比对数λ₃)是多少？在编码器的校验节点处执行的运算为模2加。Problem Statement: If the posterior probabilities p ₁ and p ₂ (log-likelihood ratio log λ ₁ , λ ₂ ) are known, then the posterior probability p ₃ (log-likelihood ratio log λ ₃ ) How much is it? The operation performed at the check node of the encoder is a modulo-2 addition.

如图7所示，为了解决上面提出的问题，构建了事件的完全组。于是，As shown in Figure 7, in order to address the issues raised above, a full set of events is constructed. then,

${λ λ}_{33} = = ln ln ((\frac{{p p}_{11} ((11 - - {p p}_{22})) + + {p p}_{22} ((11 - - {p p}_{11}))}{{p p}_{11} {p p}_{22} + + ((11 - - {p p}_{11})) ((11 - - {p p}_{22}))})) - - - - - - ((33))$

${λ λ}_{33} = = ln ln ((\frac{\frac{{e e}^{{λ λ}_{11}}}{(({e e}^{{λ λ}_{11}} + + 11))} \frac{11}{(({e e}^{{λ λ}_{22}} + + 11))} + + \frac{{e e}^{{λ λ}_{22}}}{(({e e}^{{λ λ}_{22}} + + 11))} \frac{11}{(({e e}^{{λ λ}_{11}} + + 11))}}{\frac{{e e}^{{λ λ}_{11}}}{(({e e}^{{λ λ}_{11}} + + 11))} \frac{{e e}^{{λ λ}_{11}}}{(({e e}^{{λ λ}_{11}} + + 11))} + + \frac{11}{(({e e}^{{λ λ}_{11}} + + 11))} \frac{11}{(({e e}^{{λ λ}_{22}} + + 11))}})) - - - - - - ((44))$

或or

${λ λ}_{33} = = ln ln ((\frac{{e e}^{{λ λ}_{11}} + + {e e}^{{λ λ}_{22}}}{{e e}^{{λ λ}_{11} + + {λ λ}_{22}} + + 11})) - - - - - - ((55))$

在e^λ1+1≠0，e^λ2+1≠0的条件下，Under the condition of e ^λ1 +1≠0, e ^λ2 +1≠0,

λ₃＝ln(e^λ1+e^λ2)-ln(e^λ1+λ2+1)＝E(λ₁，λ₂)-E(0，λ₁+λ₂) (6)λ ₃ =ln(e ^λ1 +e ^λ2 )-ln(e ^λ1+λ2 +1)=E(λ ₁ ,λ ₂ )-E(0,λ ₁ +λ ₂ ) (6)

其中turbo码函数E广泛地使用where the turbo code function E is widely used

E(a，b)＝ln(e^a+e^b)＝max(a，b)+ln(1+e^-|a-b|) (7)E(a,b)=ln(e ^a +e ^b )=max(a,b)+ln(1+e ^-|ab| ) (7)

因此，具有正确的符号的消息可被立即计算出。除了函数E的两个调用之外，只需执行一次加法和一次减法。Therefore, messages with the correct sign can be calculated immediately. In addition to the two calls of function E, only one addition and one subtraction need be performed.

计算对数似然比(概率解码-tanh()rule)的另一方法在(3)中示出的概率p₃可表示为：Another way to calculate the log-likelihood ratio (probabilistic decoding - tanh() rule) The probability _p3 shown in (3) can be expressed as:

p₁＝p₁(1-p₂)+p₂(1-p₁)＝p₁+p₂-2p₁p₂ (8)p ₁ =p ₁ (1-p ₂ )+p ₂ (1-p ₁ )=p ₁ +p ₂ -2p ₁ p ₂ (8)

两边都乘2并减去1，可得：Multiply both sides by 2 and subtract 1 to get:

2p₃-1＝2p₁+2p₂-4p₁p₂-1 (9)2p ₃ -1＝2p ₁ +2p ₂ -4p ₁ p ₂ -1 (9)

将右边分解成因式：Factor the right side into factors:

(2p₁-1)(2p₂-1)＝4p₁p₂-2p₁-2p₂+1 (10)(2p ₁ -1)(2p ₂ -1)＝4p ₁ p ₂ -2p ₁ -2p ₂ +1 (10)

代入损失结果，我们得到：Substituting the loss result, we get:

(2p₃-1)＝-(2p₁-1)(2p₂-1) (11)(2p ₃ -1) = -(2p ₁ -1)(2p ₂ -1) (11)

或，除2p₁-1＝0的情况之外，两边取对数：Or, except in the case of 2p ₁ -1 = 0, take the logarithm of both sides:

[ln(2p₃-1)]＝-[ln(2p₁-1)]-[ln(2p₂-1)]2p₁≠0.5 (12)[ln(2p ₃ -1)]=-[ln(2p ₁ -1)]-[ln(2p ₂ -1)]2p ₁ ≠0.5 (12)

其中该对数用λ表示如下：where the logarithm is represented by λ as follows:

$ln ln ((22 p p - - 11)) = = ln ln ((\frac{{22 e e}^{λ λ}}{11 + + {e e}^{λ λ}} - - 11)) = = ln ln ((\frac{{e e}^{λ λ} - - 11}{{e e}^{λ λ} + + 11})) - - - - - - ((1313))$

让我们考虑函数 $f (λ) = \ln (\frac{e^{λ} - 1}{e^{λ} + 1})$ 的性质，Let's consider the function $f (λ) = \ln (\frac{e^{λ} - 1}{e^{λ} + 1})$ the nature of

此函数具有以下性质：This function has the following properties:

1.偶函数f(λ)＝f(-λ)1. Even function f(λ)=f(-λ)

2.该函数在图10中绘出2. The function is plotted in Figure 10

3.该函数在0处没有定义3. The function is not defined at 0

该函数是自逆(self-inverse)函数f(f(x))＝xThe function is a self-inverse function f(f(x))=x

在校验节点处的计算的运算顺序由以下步骤给出：The order of operations for computation at a check node is given by the following steps:

1.如果在输入消息中不存在零，则输出消息符号除这一个之外通过对输入消息的符号进行异或来按标准方式来计算，否则输出消息还为零；1. If there is no zero in the input message, the output message symbols except this one are calculated in the standard way by XORing the symbols of the input message, otherwise the output message is also zero;

2.对所有输入消息用表格f(x)＝-ln((exp(x)-1)/(exp(x)+1)来进行直接转换，其中x为输入消息(在图8中绘出)；2. Carry out direct conversion to all input messages with form f(x)=-ln((exp(x)-1)/(exp(x)+1), where x is the input message (drawn in Fig. 8 );

3.根据(12)来计算转换的消息的和。3. Compute the sum of the transformed messages according to (12).

4.为得到的和来计算逆函数f的变换。(？)4. Compute the transformation of the inverse function f for the resulting sum. (?)

综述review

提供了校验节点操作的两种算法：“E展示”和“tanh()规则”。两者都没有损失并给出了ML判决。这些方法将在H/W体系结构的设计部分继续考虑。下一部分将在具有E展示的仿真器提供与turbo码的比较。Two algorithms for checkpoint operation are provided: "E display" and "tanh() rule". Both have no loss and give the ML verdict. These methods will continue to be considered in the design part of the H/W architecture. The next section will provide a comparison with turbo codes in an emulator with an E display.

仿真与Turbo码的比较Comparison between Simulation and Turbo Code

第一仿真目标是按固定速率1/2来执行比较。然后介绍了基于速率兼容的LDPC码的重复累加编码器结构。下一仿真目标是与下面表格4中指定的压缩的3GPP2 turbo解码器进行比较。The first simulation goal is to perform the comparison at a fixed rate 1/2. Then a repeat-accumulate encoder structure based on rate-compatible LDPC codes is introduced. The next simulation objective is to compare with the compressed 3GPP2 turbo decoder specified in Table 4 below.

输入信号量化Input signal quantization

如果使用E函数表格，则输入信号必须被转换为单位离差并表示为或

其中r₁和r₂为到对应星座点的距离。然后以

Δ = \frac{σ^{2}}{32}

的步长来执行8位量化。E函数表格按同样的步骤初始化。If using the E-function table, the input signal must be converted to unit dispersion and expressed as or

where r ₁ and r ₂ are the distances to the corresponding constellation points. then with

Δ = \frac{σ^{2}}{32}

Step size to perform 8-bit quantization. The E function table is initialized in the same steps.

编码参数及仿真结果Coding parameters and simulation results

在速率1/2处执行比较，信息块的大小为1000位。对LDPC IRA码，选择了不规则重复表格(图9)。在此情况下内部交织器的大小为7000。这是s＝32的s随机交织器。在交织之后，对速率1/2在校验节点以等于7的间隔执行规则的合并。The comparison is performed at rate 1/2 and the size of the information block is 1000 bits. For LDPC IRA codes, the Irregular Repeat table is selected (Figure 9). The size of the inner interleaver is 7000 in this case. This is the s random interleaver with s=32. After interleaving, regular combining is performed at check nodes for rate 1/2 at intervals equal to 7.

为了比较，选择了3GPP turbo码。For comparison, 3GPP turbo codes are chosen.

基于速率兼容的LDPC解码器的RA编码器的结构通过压缩奇偶校验符号由多路分解的级联校验节点来得到。如果分量节点具有零校验和，则在级联的校验节点的奇偶校验和强制等于零。图12说明了通过改变校验节点的大小的来自RA编码器的所有可能速率的导出。RA编码器结构保证奇偶校验和等于零。The structure of the RA encoder based on a rate-compatible LDPC decoder is obtained by demultiplexing concatenated check nodes by compressing the parity symbols. If a component node has a zero checksum, the parity checksum at the cascaded check node is forced to be equal to zero. Figure 12 illustrates the derivation of all possible rates from the RA encoder by varying the size of the check nodes. The RA encoder structure guarantees that the parity sum is equal to zero.

在编码器侧，速率兼容码通过改变锁定键“奇偶符号端”的周期而产生。在解码器侧，到校验节点的序列改变的消息的数目与奇偶符号产生周期相对应。仿真结果与3GPP2 turbo解码器的比较在图13中给出。On the encoder side, rate-compatible codes are generated by varying the period of the "parity end" of the lock key. On the decoder side, the number of sequence-changed messages to the check node corresponds to the parity symbol generation cycle. The comparison of the simulation results with the 3GPP2 turbo decoder is given in Fig. 13.

表2校验节点处的系统消息的数目Table 2 checks the number of system messages at the node

速率 rate 奇偶校验符号的产生周期-从系统节点到各校验节点的可变数目的序列改变的消息 Generation period of parity symbols - variable number of sequence-changed messages from system nodes to each check node 1/2 1/2 7 7 1/3 1/3 3-4 3-4 1/4 1/4 2-2-3 2-2-3 3/4 3/4 14 14 4/5 4/5 28 28 1/8 1/8 1 1

上表选择了重复因子α＝7，并且重复表格的最佳不规则结构在图9中示出，重复的次数证明为传输中的位数目的函数。The repetition factor α = 7 was chosen for the above table and the optimal irregular structure of the repetition table is shown in Fig. 9, the number of repetitions is shown as a function of the number of bits in the transmission.

速率兼容的LDPC IRA码相比turbo码除了极低速率1/4和极高速率(4/5)之外没有损失。重复表是最佳的以便在主要速率(1/2、1/3、2/3、3/4)上得到最佳性能。在此情况下，速率1/8比速率1/4更差，即速率为1/4时，数据应被重复两次，而不是在速率为1/8时的编码。此外，与turbo码相比，IRA码的出错底限(error floor)低得多。The rate-compatible LDPC IRA code has no loss compared to the turbo code except for the very low rate 1/4 and the very high rate (4/5). Repeating tables are optimal for best performance on major rates (1/2, 1/3, 2/3, 3/4). In this case, rate 1/8 is worse than rate 1/4, i.e. at rate 1/4 the data should be repeated twice instead of being encoded at rate 1/8. In addition, IRA codes have a much lower error floor than turbo codes.

平均重复因子7是基于最大码率1/8来选择的。The average repetition factor of 7 is chosen based on the maximum code rate of 1/8.

同样应注意上述的码为速率兼容码，即它形成了可变速率码系列，允许了HARQ-II的实现。It should also be noted that the above code is a rate compatible code, ie it forms a family of variable rate codes, allowing the implementation of HARQ-II.

下表是速率组，并给出了用于调制符号的具有来自SNR的双极大解调器的仿真结果。The table below is the rate group and presents the simulation results of a bipolar demodulator with SNR derived for the modulated symbols.

MCS索引 MCS index 码率 code rate QAM QAM 有效载荷(bits/TTI(2ms)) Payload (bits/TTI(2ms)) 用户速率(Mbits/s) User Rate(Mbits/s) 1 1 0.125 0.125 2 2 2428 2428 1.21 1.21 2 2 0.200 0.200 2 2 3863 3863 1.93 1.93 3 3 0.250 0.250 2 2 4856 4856 2.43 2.43 4 4 0.333 0.333 2 2 6512 6512 3.26 3.26 5 5 0.500 0.500 2 2 9824 9824 4.91 4.91 6 6 0.667 0.667 2 2 13135 13135 6.57 6.57 7 7 0.800 0.800 2 2 15785 15785 7.89 7.89 8 8 0.500 0.500 4 4 19759 19759 9.88 9.88 9 9 0.667 0.667 4 4 26382 26382 13.19 13.19 10 10 0.800 0.800 4 4 31681 31681 15.84 15.84 11 11 0.667 0.667 6 6 39629 39629 19.81 19.81 12 12 0.750 0.750 6 6 44596 44596 22.30 22.30 13 13 0.800 0.800 6 6 47577 47577 23.79 23.79

表格3速率组Table 3 Rate Group

IRA-7码的性能结论Performance conclusion of IRA-7 code

存在根据调制符号能量对噪声比的BER、FER曲线。给出了表格4的所有MCS。余下的问题是各速率的码矩阵是不同的。在这个项目中根据本项目的目标开发的码是速率兼容的(1/8-4/5)。这意味着高速率通过压缩母码来得到。编码的系统部分必须是相同且稳定的。然而，得到的结果对于编码的比较给出了良好的基准测试。There are BER, FER curves according to modulation symbol energy to noise ratio. All MCS for Table 4 are given. The remaining problem is that the code matrix is different for each rate. The codes developed in this project according to the goals of this project are rate compatible (1/8-4/5). This means that high rates are obtained by compressing the mother code. The system part of the encoding must be identical and stable. However, the obtained results give a good benchmark for comparison of encodings.

H/W体系结构设计及复杂性分析H/W Architecture Design and Complexity Analysis

基本LDPC解码器体系结构Basic LDPC Decoder Architecture

图15示出了示例解码器结构。Figure 15 shows an example decoder structure.

这种体系结构的主要的实现问题在于RAM存取的FPGA限制。更具体地说，Virtex 812EM实现了对4k存储块的双端口存取。也就是说，在一个时钟内两个数可从这样的区中读出，或者一个数可读出而另一个可被写入。因此，并行消息处理的实现需要在可存取的存储体中布置来自变量节点的消息，以便从不同存储体读出由校验节点处理器处理的消息，并且写入不同的存储体以避免存取冲突。The main implementation problem with this architecture is the FPGA limitation of RAM access. More specifically, the Virtex 812EM implements dual-port access to 4k memory blocks. That is, two numbers can be read from such an area within one clock, or one number can be read and the other can be written. Therefore, the implementation of parallel message processing requires arranging messages from variable nodes in accessible memory banks in order to read messages processed by check node processors from different memory banks and write to different memory banks to avoid memory Take the conflict.

基于“解码器-第一码设计”规则在图16中示出了并行校验节点处理器的结构。让我们考虑该解码器的运算速度估计：The structure of the parallel check node processor is shown in FIG. 16 based on the "decoder-first code design" rule. Let's consider an estimate of the operational speed of this decoder:

$T T = = \frac{{F f}_{d d} * * Z Z * * R R}{α α * * I I}$

其中Fd为FPGA时钟速率，z为计算的并行因子，R是码率，α是码符号重复因子(均值)，I为迭代次数。Among them, Fd is the FPGA clock rate, z is the calculation parallel factor, R is the code rate, α is the code symbol repetition factor (mean value), and I is the number of iterations.

Z等于并行计算消息的数目。在一个FPGA时钟处理的相应数据位的数目是按迭代次数计算并且分开以便获得吞吐量及解码器运算速度。以下公式被施加到并行LDPC解码器以计算其运算速度。Z is equal to the number of parallel computing messages. The number of corresponding data bits processed in one FPGA clock is counted in iterations and divided in order to obtain throughput and decoder operation speed. The following formula is applied to the parallel LDPC decoder to calculate its operation speed.

交织器设计Interleaver Design

存在两种交织器设计的途径。There are two approaches to interleaver design.

●代数●Algebra

●随机●Random

考察了代数交织器对于速率R＞1/2(即2/3、3/4、4/5)的性能损失。速率兼容解码器在速率为1/8-4/5的范围并不适合。The performance loss of the algebraic interleaver for rates R > 1/2 (ie 2/3, 3/4, 4/5) is investigated. Rate-compatible decoders are not suitable for rates in the 1/8-4/5 range.

具有RA编码器结构的随机交织器集中在本工作中。Random interleavers with RA encoder structures are focused in this work.

对交织器的需求可表示为：The requirement for an interleaver can be expressed as:

●最大并行因子●Maximum parallelism factor

●对给定的并行因子无性能损失(无低权重码字)● No performance loss for a given parallelism factor (no low weight codewords)

考虑RA码结构，可作出以下结论：Considering the RA code structure, the following conclusions can be made:

●奇偶校验符号无需交织器，只需按因子2重复。● The parity symbol does not need an interleaver, it only needs to be repeated by a factor of 2.

●系统符号需要按至少为3的因子重复以在进行交织之前在● Systematic symbols need to be repeated by a factor of at least 3 to be in the

Tanner图(图17)上表示每个边沿。Each edge is represented on the Tanner diagram (Fig. 17).

随机交织器数目需要存储。对于1000位的块按重复因子7的实现需要具有大小为7000的交织器。它取7000×14位。不工作的数目的产生是不好的想法，因为它占用FPGA时钟。将交织器分成小的交织器(其数目等于并行因子)是解决方案。每个小交织器上载到FGPA RAM块中。因此，来自交织器的每个数需要8位(参见图18)。The random interleaver number needs to be stored. An implementation with a repetition factor of 7 for a block of 1000 bits requires an interleaver of size 7000. It takes 7000x14 bits. Generating numbers that don't work is bad idea because it takes FPGA clock. Dividing the interleaver into small interleavers (the number of which is equal to the parallelism factor) is the solution. Each small interleaver is uploaded into the FPGA RAM block. Therefore, each number from the interleaver requires 8 bits (see Figure 18).

高FPGA板上的RAM块的大小是很大的(至少18k)。该块是不会满的并对于存储8位或16位没有区别。The size of the RAM blocks on tall FPGA boards is large (at least 18k). The block is never full and makes no difference for storing 8 or 16 bits.

好的交织器可通过随机搜索来发现。A good interleaver can be found by random search.

通过使用2种以下技术，交织器存储器的需要还可进一步降低：The need for interleaver memory can be further reduced by using the following 2 techniques:

●偶奇对称性●even-odd symmetry

●扩展的交织器●Extended interleaver

偶奇交织器是对称交织器，它允许将每一个奇位置用偶位置交换，反之亦然。这种交织器结构满足以下两个限制：An even-odd interleaver is a symmetric interleaver that allows swapping every odd position with an even position and vice versa. This interleaver structure satisfies the following two constraints:

●奇到偶的转换：imod2≠π(i)mod2，i●Odd to even conversion: imod2≠π(i)mod2, i

●对称性：π(i)＝jπ(j)＝i●Symmetry: π(i)=jπ(j)=i

假设在交织器向量中只存储了奇位置。所有存储的地址然后为偶数，意味着每个地址的二进制表示中的LSB总是零。因此提供了额外的存储器节省。奇偶交织器的运算示出在图19中。Assume only odd positions are stored in the interleaver vector. All stored addresses are then even, meaning that the LSB in the binary representation of each address is always zero. Additional memory savings are thus provided. The operation of the parity interleaver is shown in FIG. 19 .

为了保持奇偶对称性质，虽然扩展了交织器的长度，但是我们需要在原交织器中在每第二项之后插入两个未定义的元素。这种改进确保了在原交织器中的偶位置上的各元素在扩展之后仍保持在偶位置，反之亦然。In order to maintain the property of parity symmetry, although the length of the interleaver is extended, we need to insert two undefined elements after every second item in the original interleaver. This improvement ensures that elements in even positions in the original interleaver remain in even positions after expansion, and vice versa.

速率兼容校验节点处理器Rate Compatible Check Node Processor

考察速率兼容校验节点处理器的体系结构。通过压缩奇偶校验符号并通过级联由这些符号划分(demaroated)的基本校验节点来获得高速率。基本的校验节点处理器结构在图21中以E展示示出，其中：运算+意味着“箱求和”装置，八边形是奇偶校验节点消息，正方形是系统变量节点消息。这些处理器的并行应用使得能实现速率1/8、1/4、1/3。Examines the architecture of rate compatible check node processors. High rates are obtained by compressing parity symbols and by concatenating elementary check nodes demaroated by these symbols. The basic check node processor structure is shown at E in Figure 21, where: op + means "bin sum" means, octagons are parity check node messages, squares are system variable node messages. Parallel application of these processors enables rates 1/8, 1/4, 1/3.

以下变形可能从速率1/2开始。The following transformations may start at rate 1/2.

所考虑的变形具有8个“箱求和”时钟的延时，并且在第8个时钟同时需要7个“箱求和”模块，并且在所有其他时钟需要2个模块。该处理器校验节点的另一种实现的变形也是可能的。The considered variant has a delay of 8 "bin-sum" clocks and requires 7 "bin-sum" modules simultaneously on the 8th clock and 2 modules on all other clocks. Another implementation variant of the processor check node is also possible.

在第一个时钟需要四个模块，第二个时钟6个，第三个时钟8个，以及最后一个时钟7个。模块的峰值增加到8，并且所需的时钟的数目减少为4。此外，该处理器可被用在两个速率：1/3(接近1/3)及1/2。校验节点3的结果在第三个时钟准备好。Four modules are required on the first clock, 6 on the second clock, 8 on the third clock, and 7 on the last clock. The peak number of modules is increased to 8, and the number of required clocks is reduced to 4. Furthermore, the processor can be used at two rates: 1/3 (close to 1/3) and 1/2. The result of check node 3 is ready on the third clock.

然而，为了将速率调整到1/3，在校验节点中的合并在可变周期内执行：3-4，并且所考虑的体系结构按3产生校验节点。这就导致校验节点实现对于速率1/4、1/3、1/2的以下变形，如图21、24所示。However, to adjust the rate to 1/3, the merging in check nodes is performed in variable cycles: 3-4, and the considered architecture produces check nodes by 3. This results in the check nodes implementing the following transformations for rates 1/4, 1/3, and 1/2, as shown in Figures 21 and 24.

有“1”的单元对于对应于逻辑单元(1)的所选量化用最大的数来初始化。Cells with "1" are initialized with the largest number for the selected quantization corresponding to logic cell (1).

时钟：clock:

●第一个时钟→6个“箱求和”模块1st clock → 6 "bin summation" modules

●第二个时钟→4+4+3＝11个“箱求和”模块-峰值负载2nd clock → 4+4+3 = 11 "bin-summing" modules - peak load

●第三个时钟→6个“箱求和”模块●Third clock → 6 "bin summation" modules

●第四个时钟→7个“箱求和”模块4th clock → 7 "bin summation" modules

因此，对于速率兼容的处理器校验节点，11个“箱求和”模块(最大)及7个“箱求和”模块(最小)是必需的。计算延时占用4个时钟的“箱求和”模块(最小)，以及7个时钟的“箱求和”模块(最大)。Thus, for a rate-compatible processor check node, 11 "bin-sum" modules (maximum) and 7 "bin-sum" modules (minimum) are required. Computational delays take 4 clocks of the "bin sum" block (minimum), and 7 clocks of the "bin sum" block (maximum).

速率组构造在图25中示出。The rate group configuration is shown in FIG. 25 .

因此，速率2/3、4/5从相当容易实现的速率组中被留下。Thus, rates 2/3, 4/5 are left out of the set of rates that are fairly easy to implement.

图26是校验节点处理器2/3的示例。Figure 26 is an example of check node processor 2/3.

图27是校验节点处理器4/5的示例。Figure 27 is an example of check node processor 4/5.

基于复杂性降低的节点处理器的ln((exp(x)-1)/(exp(x)+1))函数(基于tanh()规则的体系结构)。ln((exp(x)-1)/(exp(x)+1)) function based on complexity-reduced node processors (architecture based on the tanh() rule).

复杂性降低的另一体系结构在图28中示出。Another architecture of reduced complexity is shown in FIG. 28 .

LUT(表格4)用类型-ln((exp(x)-1)/(exp(x)+1)的直接变换来表示。由于该函数的性质，相同的表格也被用在正向和反向变换中。The LUT (table 4) is represented by a direct transformation of the type -ln((exp(x)-1)/(exp(x)+1). Due to the nature of the function, the same table is also used for the forward and inverse to transform.

表4 LUT-6位f(x)＝{ln((exp(x/16)-1)/(exp(x/16)+1)}*16Table 4 LUT-6 bits f(x)＝{ln((exp(x/16)-1)/(exp(x/16)+1)}*16

x x f(x) f(x) x x f(x) f(x) x x f(x) f(x) x x f(x) f(x) 12345678 12345678 5544383330272523 5544383330272523 1718192021222324 1718192021222324 12111099887 12111099887 3334353637383940 3334353637383940 44433333 44433333 4950515253545556 4950515253545556 11111111 11111111

910111213141516 910111213141516 2119181615141312 2119181615141312 2526272829303132 2526272829303132 76665554 76665554 4142434445464748 4142434445464748 22222222 22222222 5758596061626364 5758596061626364 11111111 11111111

位宽度增加超过6位不是问题。在这种情况下，在没有零时该输入值按7位来量化。第六位为软判决模块，第7位为符号位。在这种情况下LUT可加上零f(0)＝0。这个零没有任何物理意义，并会被用在可变速率解码器的不同节点处理器的合并。Increasing the bit width beyond 6 bits is not a problem. In this case, the input value is quantized with 7 bits without zeros. The sixth bit is the soft decision module, and the seventh bit is the sign bit. In this case the LUT may add zero f(0)=0. This zero has no physical meaning and is used for combining different node processors in variable rate decoders.

加法器图28为传统的整数加法器。图28示出了输出消息检测模块的原理，它应通过输出消息符号定义原理来完成。在符号处理器处的计算类似于模块定义原理的计算，由“异或”代替加法来区分。同样变量节点结构必须通过从符号格式到二进制补码的变换来完成，如符号加法(在变量节点处执行)更便利地按这样的格式执行。校验节点处理器2+2的完整结构在图29中示出。注意，LUT变换在IRA码中无需奇偶校验符号，如在奇偶校验节点处的它们的处理考虑简单的转置(图31)一样。LUT变换在初始化的同时执行(图30)。在图32中示出了用于可变速率解码器的含有复合节点处理器的结构的构成节点处理器。该结构假定使用两个节点处理器，其中压缩的奇偶校验符号由逻辑单元(1)用零幅度初始化，并且这个符号被包含在两个构成处理器中。在复合节点处理器处得到的消息的符号通过具有第二构成节点处理器的输出符号的相应构成节点处理器消息符号的“异或”获得。在构成节点处理器处得到的消息幅值由具有第二构成处理器的输出幅值的相应构成节点处理器得到的幅度相加产生。变量节点处理器的结构在图33中示出。输入消息幅值由LUT在没有变换符号的前提下用同样的表格来变换。所得到的值被变换为二进制补码。在求和之后，输出消息由这些消息变换为带符号的整数来产生。Adder Figure 28 shows a conventional integer adder. Fig. 28 shows the principle of the output message detection module, which should be completed by the principle of output message symbol definition. Computation at the symbolic processor is similar to that of the module definition principle, distinguished by "exclusive or" instead of addition. Also variable node structure must be done by conversion from signed format to two's complement, as signed addition (performed at variable nodes) is more conveniently performed in such a format. The complete structure of check node processor 2+2 is shown in FIG. 29 . Note that LUT transformations do not require parity symbols in the IRA code, as their processing at the parity nodes considers a simple transposition (Fig. 31). LUT transformation is performed at the same time as initialization (Fig. 30). In Fig. 32 there is shown a constituent node processor for a variable rate decoder having a structure of multiple node processors. The architecture assumes the use of two node processors, where a compressed parity symbol is initialized by logic unit (1) with zero magnitude, and this symbol is contained in two constituent processors. The sign of the message obtained at the compound node processor is obtained by "exclusive OR" of the corresponding constituent node processor message sign with the output symbol of the second constituent node processor. The message magnitude obtained at a constituent node processor is produced by summing the magnitudes obtained by the corresponding constituent node processor with the output magnitude of the second constituent processor. The structure of the variable node processor is shown in FIG. 33 . The input message amplitude is transformed by the LUT using the same table without changing the sign. The resulting value is converted to two's complement. After summing, output messages are produced by converting these messages to signed integers.

变量节点处理器的结构，处理较大数目的消息，类似于图33所示。在结果中，所有变换的输入消息的具有符号的和被写入到“输出”单元，作为软数据位判决，输出消息由来自“输出”的相应输入消息的LUT变换的减法得到。The structure of the variable node processor, which handles a larger number of messages, is similar to that shown in Figure 33. In the result, the signed sum of all transformed input messages is written to the "Output" unit, as a soft data bit decision, the output message is obtained by the subtraction of the LUT transformation of the corresponding input message from "Output".

实现问题及运算速度估计Implementation Issues and Calculation Speed Estimation

重复累加编码原理的选择因为如下原因作出：The choice of the repeat-accumulate coding principle was made for the following reasons:

●尽可能简单地编码● Coding as simple as possible

●码含有系统及奇偶校验部分The code contains the system and parity part

●奇偶校验符号的通常交织器●Usual interleaver for parity symbols

●减少到最小的奇偶校验符号重复(2-两次)。- Reduced to minimal parity symbol repetition (2-twice).

运算速度估计公式可不带码率写成：The calculation speed estimation formula can be written without code rate as:

$T T = = \frac{Z Z * * {F f}_{d d}}{I I * * α α} - - - - - - ((1515))$

其中z是交织器并行因子，α是系统位的重复因子。Fd为FPGA板时钟速率，I为迭代次数。where z is the interleaver parallelism factor and α is the repetition factor of systematic bits. Fd is the FPGA board clock rate, and I is the number of iterations.

以下问题在下一部分考虑：如何将并行数据流上载到具有不规则重复的交织器上。将不同程度重复的符号合并到具有固定速率的块是可能的，其长度等于交织器的并行因子。The following question is considered in the next section: how to upload parallel data streams to an interleaver with irregular repetition. It is possible to combine symbols repeated to different degrees into blocks with a fixed rate, whose length is equal to the parallelism factor of the interleaver.

不规则码Irregular code

在变量节点处理器处计算的目的被减少到除为其响应消息被计算的消息之外的所有节点有关的消息之和的计算。The purpose of the calculation at the variable node processor is reduced to the calculation of the sum of all node-related messages except the message for which the response message is calculated.

对于变量奇偶校验节点，在两个情况下，这样的运算是简单的：交换它们的位置2次。这样的运算在处理器校验节点成为系统节点交织的模拟之后直接被执行。为了简化变量节点的处理，选择了不规则重复表格以维持重复的符号的数目数倍于用在消息存储中的存储体的数目。在这种情况下，这个数等于28，它也是可由校验节点处理器并行处理的消息的最大数。显然，并行处理消息的数目不能大于这个数。For variable parity nodes, such an operation is simple in both cases: swap their positions 2 times. Such operations are performed directly after the processor check node becomes a simulation of the interleaving of the system node. In order to simplify the processing of variable nodes, the irregular repetition table was chosen to maintain the number of repeated symbols a multiple of the number of banks used in the message store. In this case, this number is equal to 28, which is also the maximum number of messages that can be processed in parallel by a check node processor. Obviously, the number of messages processed in parallel cannot be greater than this number.

不规则重复表格可按以下方式来组织：Irregularly repeating tables can be organized as follows:

存在重复的符号的可容许的序列，以致重复的符号的数目为7的倍数并在28之下。There is an admissible sequence of repeated symbols such that the number of repeated symbols is a multiple of 7 and below 28.

·3335-4个信息符号被全部重复14次，图343335-4 information symbols are all repeated 14 times, Figure 34

·7-任何数目的消息可被重复7次，图357 - Any number of messages can be repeated 7 times, Figure 35

·113-第一位被重复11次，且下一位被重复3次113 - the first digit is repeated 11 times, and the next digit is repeated 3 times

·1315-数据位被全部重复28次1315 - data bits are all repeated 28 times

·28-一个位的重复的最大数目28 - the maximum number of repetitions of a bit

除了来自变量节点的输出消息计算之外，输出软判决由处理器为解码器产生。这种软判决可直接用于在迭代期间上载的数据。本文中运算“+”为带符号求和。In addition to output message computations from variable nodes, output soft decisions are generated by the processor for the decoder. Such soft decisions can be used directly for data uploaded during iterations. In this paper, the operation "+" is signed summation.

在图36和图37上示出了硬件约束(交织器及重复表)的码设计损失。如图可见，不存在相对于turbo码的大的块误码损失，虽然观测到了相对于随机IRA码的该损失。Code design penalties for hardware constraints (interleaver and repetition table) are shown in Fig. 36 and Fig. 37 . As can be seen, there is no large block error penalty relative to turbo codes, although this penalty is observed relative to random IRA codes.

运算速度估计为The operating speed is estimated to be

T＝(z*Fd)/(I*Alpha)＝(28*Fd)/(I*7)。今数目迭代为I＝24，且Fd＝100MHz(28*100MHz)/(24*7)＝100MHz/6＝15MBps。最大32个奇偶校验符号需要并行地上载，因此需要最小16块来存储它们。存储器分配7000/250+16＝28+16＝44RAM块最小。T=(z*Fd)/(I*Alpha)=(28*Fd)/(I*7). Now the number of iterations is I=24, and Fd=100MHz(28*100MHz)/(24*7)=100MHz/6=15MBps. A maximum of 32 parity symbols needs to be uploaded in parallel, so a minimum of 16 blocks is required to store them. Memory allocation 7000/250+16=28+16=44 RAM block minimum.

简单压缩或校验节点级联Simple compression or checkpoint cascading

简单压缩工作，但与校验节点级联相比，在FER＝0.01时有1dB的损失。然而校验节点级联的算法(图32、图26、图27)需要更多的逻辑FPGA板。仿真结果在图38及图39中给出。Simple compression works, but has a 1dB penalty at FER=0.01 compared to check node concatenation. However, the algorithm for cascading check nodes (Fig. 32, Fig. 26, Fig. 27) requires more logical FPGA boards. The simulation results are given in Figure 38 and Figure 39.

规则码rule code

为增加吞吐量及运算速度，实现了规则重复累加码。重复因子降低为3。这就意味着每一个系统位仅被重复3次。并行因子72通过减小交织器分集(S因子)来实现。交织器大小为9000且系统部分大小为3000。码率为1/2。In order to increase the throughput and operation speed, the regular repetitive accumulation code is realized. Repetition factor reduced to 3. This means that each systematic bit is repeated only 3 times. The parallelism factor 72 is achieved by reducing the interleaver diversity (S-factor). The interleaver size is 9000 and the systematic part size is 3000. The code rate is 1/2.

规则码的性能损失被忽略。在并行数据流的上载中不存在问题。The performance penalty of regular codes is ignored. There is no problem in the upload of parallel data streams.

参见图40及41。See Figures 40 and 41.

运算速度估计为The operating speed is estimated to be

T＝(z*Fd)/(I*Alpha)＝(28*Fd)/(I*7)。令迭代数为I＝24，且Fd＝100MHz(72*100MHz)/(24*3)＝100MHz＝100Mbit/s。最大48个奇偶校验符号需要并行地上载，因此最小需要24块来存储它们。存储器分配9000/125+48＝72+48＝120RAM块最小T=(z*Fd)/(I*Alpha)=(28*Fd)/(I*7). Let the number of iterations be I=24, and Fd=100MHz(72*100MHz)/(24*3)=100MHz=100Mbit/s. A maximum of 48 parity symbols needs to be uploaded in parallel, so a minimum of 24 blocks is required to store them. Memory allocation 9000/125+48=72+48=120 RAM block minimum

减小重复因子的影响Reduce the effect of repetition factor

以下仿真给出了这个问题的答案。使用了相同的交织器并具有数据重复因子3、2、1。第一个码以速率3000/(3000+3000)＝1/2运算，下一个以速率4500/(4500+3000)＝3/5运算，最后一个以速率9000/(9000+3000)＝3/4运算。The following simulation gives the answer to this question. The same interleaver was used with data repetition factors 3,2,1. The first code is calculated at a rate of 3000/(3000+3000)=1/2, the next one is calculated at a rate of 4500/(4500+3000)=3/5, and the last code is calculated at a rate of 9000/(9000+3000)=3/ 4 operations.

重复因子由3减小到2有3dB的损失。重复因子由3减小到1在BER＝10^-6处有7dB的损失。参见图42。There is a 3dB loss in reducing the repetition factor from 3 to 2. Reducing the repetition factor from 3 to 1 has a 7dB loss at BER=10 ^-6 . See Figure 42.

简单压缩的影响Effect of Simple Compression

简单压缩工作(2/3，3/4，4/5)但对于本文中描述的校验节点级联的算法有1db的损失。参见图43。Simple compression works (2/3, 3/4, 4/5) but has a 1db penalty for the checkpoint cascading algorithm described in this paper. See Figure 43.

减小解码迭代次数的影响Reduce the impact of the number of decoding iterations

图43、44及45中示出了示例。迭代次数由100减小到24有0.3dB的损失。迭代次数由100减小到10在BER＝10^-6处有1dB的损失。Examples are shown in FIGS. 43 , 44 and 45 . There is a loss of 0.3dB when the number of iterations is reduced from 100 to 24. Reducing the number of iterations from 100 to 10 has a loss of 1 dB at BER=10 ⁻⁶ .

按照上面的讲授，本发明的大量的改进及变化都是可能的。因此会理解在所附的权利要求书的范围内，本发明可按不同于本文具体描述地被实现。Numerous modifications and variations of the present invention are possible in light of the above teaching. It is therefore to be understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described herein.

Claims

1. one kind is suitable for the LDPC encoder with linear complexity that the generation system exports and parity check is exported, and described encoder comprises:

Duplicator is realized irregular duplication code;

Interleaver interweaves to described duplicator output execution;

Accumulator is carried out the output of described interleaver and to be added up and export described parity check output.

2. LDPC encoder as claimed in claim 1, wherein said interleaver be S at random or the congruence interleaver.

3. LDPC encoder as claimed in claim 1, wherein said accumulator is carried out irregular adding up.

4. LDPC encoder as claimed in claim 1, wherein said accumulator executing rule adds up.

5. LDPC encoder as claimed in claim 1 also is included in the parallel-to-serial function between described duplicator and the described interleaver.

6. LDPC encoder as claimed in claim 1 changes to come by parametrization by the repeat pattern of described duplicator and the sequence of described interleaver.

7. LDPC encoder as claimed in claim 1, it is best that wherein said repeat pattern and sequence change.

8. LDPC encoder as claimed in claim 1, wherein said S random interleaver are half random algorithm with refusal, and interweaving in advance continuous to s provides the back interleaved distance that is not less than s,

s \leq \sqrt{{&OverBar;}_{2}^{N}} .

9. LDPC encoder as claimed in claim 1, wherein said LDPC sign indicating number can be represented by following parity matrix with double diagonal line structure:

H_{b 2} = [h_{b} | H_{b 2}^{'}]

10. LDPC encoder as claimed in claim 1, wherein whole sign indicating number is expressed as follows by matrix form:

H = [\begin{matrix} P_{0,0} & P_{0,1} & P_{0,2} & \cdot \cdot \cdot & P_{0, n_{b} - 2} & P_{0, n_{b} - 1} \\ P_{1,0} & P_{1,1} & P_{1,2} & \cdot \cdot \cdot & P_{1, n_{b} - 2} & P_{1, n_{b} - 1} \\ P_{2,0} & P_{2,1} & P_{2,2} & \cdot \cdot \cdot & P_{2, n_{b} - 2} & P_{2, n_{b} - 1} \\ . & . & . & . & . \\ . & . & . & . . . & . & . \\ . & . & . & . & . \\ P_{m_{b} - 1,0} & P_{m_{b} - 1,1} & P_{m_{b} - 1,2} & . . . & P_{m_{b} - 1, n_{b} - 2} & P_{m_{b} - 1, n_{b} - 1} \end{matrix}] = P^{H_{b}}

Wherein H is the matrix of big or small m * n, and n is that the length and the m of described sign indicating number is the number of parity check bit in the described sign indicating number, P _{1, j}Be move to right in unit matrix or the z * z null matrix one of one group of z * z;

Described matrix H is m according to size _b* n _bThe binary radix matrix H _bExpansion, wherein n=zn _bAnd m=zm _b, and z is positive integer, described basic matrix is by unit matrix that each the 1 usefulness z * z in the described basic matrix is moved to right, and each 0 usefulness z * z null matrix is replaced expanding;

With H _bBe divided into two parts, wherein H _B1Corresponding with system bits, and H _B2Corresponding with parity check bit;

With H _B2The part separated into two parts, wherein vectorial h _bHave strange weight, and H ' _B2Equal 1 when having matrix element at the capable j row of i place at i=j, i=j+1, all the other are 0 double diagonal line structure:

H_{b 2} = [h_{b} | H_{b 2}^{'}]

H wherein _b(0)=1, h _b(m-1)=1, and the 3rd the value h _b(j), 0＜j＜(m _b-1) equals 1.

11. LDPC encoder as claimed in claim 1 also is suitable for allowing based on the conventional coders/decoder with rate-compatible check node processor structural feature to the structure of one group of different code check and the structure based on the speed of compression to being complementary with the check-node cascade.

12. one kind has, and to avoid a plurality of weights in the matrix of having expanded be the LDPC encoder of the basic matrix structure of 1 row.

13. a LDPC encoder of realizing the LDPC sign indicating number, described LDPC sign indicating number can be represented by following parity matrix with double diagonal line structure:

H_{b 2} = [h_{b} | H_{b 2}^{'}]

14. LDPC encoder as claimed in claim 13, wherein whole sign indicating number is expressed as follows by matrix form:

H = [\begin{matrix} P_{0,0} & P_{0,1} & P_{0,2} & . . . & P_{0, n_{b} - 2} & P_{0, n_{b} - 1} \\ P_{1,0} & P_{1.1} & P_{1,2} & . . . & P_{1, n_{b} - 2} & P_{1, n_{b} - 1} \\ P_{2,0} & P_{2,1} & P_{2,2} & . . . & P_{2, n_{b} - 2} & P_{2, n_{b} - 1} \\ . & . & . & . & . \\ . & . & . & . . . & . & . \\ . & . & . & . & . \\ P_{m_{b} - 1,0} & P_{m_{b} -1,1} & P_{m_{b} - 1,2} & . . . & P_{m_{b} - 1, n_{b} - 2} & P_{m_{b} - 1, n_{b} - 1} \end{matrix}] = P^{H_{b}}

15. a given information sequence s carries out the LDPC coding to determine the method for parity sequences p, said method comprising the steps of:

The k that described information sequence s is divided into the z position _b=n _b-m _bGroup makes this grouping s represent with u,

u＝[u(0)u(1)…u(k _b-1)]

Wherein each element of u is following column vector:

u(i)＝[s _ks _k+1…s _(i+1)＝-1] ^r

Matrix H uses a model _b, in the group of z, determine described parity sequences p, make the parity sequences p that is grouped represent with v,

v＝[v(0)v(1)…v(m _b-1)]，

Wherein each element of v is following column vector

v(i)＝[p _kp _k+1…p _(i+1)＝-1] ^T

Carry out initialization step to determine v (0);

Carry out recurrence with according to v (i), 0≤i≤m _b-2 determine v (i+1).

16. method as claimed in claim 15, wherein:

The form of v (0) reaches formula to be passed through H _bRow summation derive to obtain

P_{p (x_{,} k_{n})} v (0) = Σ_{j = 0}^{k_{b} - 1} Σ_{i = 0}^{m_{p} - 1} P_{p (i, j)} u (j) - - - (1)

Wherein x is non-negative and azygous h for its clauses and subclauses _bLine index 1≤x≤m _b-2, and P _iRepresent the z of i ring shift right * z unit matrix by size, equation (1) is by multiply by P ^-1 _{P (x, kb)}Come v (0) is found the solution, and

P_{p (x, k_{n})}^{- 1} = P_{2 - p (x, k_{b}),}

Because p is (x, k _b) the expression cyclic shift.

17. method as claimed in claim 16, wherein said recurrence are according to following regulation:

v (1) = Σ_{j = 0}^{k_{b} - 1} P_{p (i, j)} u (j) + P_{p (i, k_{b})} v (0), i = 0, - - - (2)

v (i + 1) = Y (i) + Σ_{j = 0}^{k_{b} - 1} P_{p (i, j)} u (j) + P_{p (i, k_{n})} v (0), i = 1, . . ., m_{b} - 2 - - - (3)

Wherein

P _-1≡0 _z×z。

18. a LDPC decoder comprises:

Parallel node processing structure, the code check and the interleaver that are suitable for any selection are selected, and are used for the sign indicating number according to any one realization of claim 1 to 17 is decoded.