低密度奇偶校验码英文翻译

低密度奇偶校验码

4 .1 Introduction

Chapter 3 analyzed the probability of decoding error for (n, j, k) codes on various binary-input channels using maximum-likelihood decoding. Maximum-likelihood decoding is a convenient concept since it minimizes the probability of decoding error and thus measure the effectiveness of a code apart from any particular decoding scheme. However, implementing a maximum-likelihood decoder that actually compares the received sequence with all possible code words is a most unattractive possibility; this is particularly true for long block lengths, since the size of the code set grows exponentially with block length. A decoder that is relatively simple in terms of equipment, storage, and computation is more desirable even if it moderately increases the probability of error. If the lower probability of error is required, one can simply increase the block length of the code.

Two decoding schemes will be described here that appear to achieve a reasonable balance between complexity and probability of decoding error. The first is particularly simple but applicable only to the BSC at rates far below capacity. The second scheme, which decodes directly from the a posteriori probabilities at the channel output is more promising but can be understood more easily after the first scheme is described.

In the first decoding scheme, the decoder computes all the parity-checks and then changes any digit that is contained in more than some fixed number of unsatisfied parity-check equations. Using these new values, the parity checks are recomputed, and the process is repeated until the parity checks are all satisfied.

If the parity-check sets are small, this decoding procedure is reasonable, since most of the parity-check sets will contain either one transmission error or no transmission errors. Thus when most of the parity-check equations checking on a digit are unsatisfied, there is a strong indication that that digit is in error. For example, suppose a transmission error occurred in the first digit of the code in Figure 2.1. Then parity checks 1,6,and 11 would be violated, and all three parity-check equations checking digit 1 would be violated. On the

other hand, at most, one of the three equations checking on any other digit in the block would be violated.

To see how an arbitrary digit d can be corrected even if its parity-check sets contain more than one transmission error, consider the tree structure in Figure 4.1. Digit d is represented by the node at the base of the tree, and each line rising from this node represents one of the parity-check sets containing digit d. The other digits in these parity-check sets are represented by the nodes on the first tier of the tree. The lines rising from tier 1 to tier 2 of the tree represent the other parity-check sets containing the digits on tier 1, and the nodes on tier 2 represent the other digits in those parity-check sets. Notice that if such a tree is extended to many tiers, the same digit might appear in more than one place, but this will be discussed in Section 4.2

Assume now that both digit d and several of the digits in the first tier are transmission errors. Then on the first decoding attempt, the error-free digits in the second tier and their parity-check constraints will allow correction of errors in the first tier. This in turn will allow correction of digit d on the second decoding attempt. Thus digit and parity-check equations can aid in decoding a digit seemingly unconnected with them. The probabilistic decoding scheme to be described next utilizes these extra digits and extra parity-check

equations more systematically.

Figure 4.1: Parity-check set tree

4.2 Probabilistic Decoding

Assume that the code words from an (n, j, k) code are used with equal probability on an arbitrary binary-input channel. For any digit d, using the notation of Figure 4.1, an

iteration process will be derived that on the mth iteration computes the probability that the transmitted digit in position d is a 1 conditional on the received symbols out to and including the mth tier. For the first iteration, we can consider digit d and the digits in the first tier to form a subcode in which all sets of the digits that satisfy the j parity-check equations in the tree have equal probability of transmission.

Consider the ensemble of events in which the transmitted digits in the positions of d and the first tier are independent equiprobable binary digits, and the probabilities of the received symbols in these positions are determined by the channel transition probabilities Px(y). In this ensemble the probability of any event conditional on the event that the transmitted digits satisfy the j parity-check equations is the same as the probability of an event in the subcode described above. Thus, within this ensemble we want to find the probability that the transmitted digit in position d is a 1 conditional on the set of received symbols {y} and on the event S that the transmitted digits satisfy the j parity-check equations on digit d. We write this as

Pr[xd1|{y},S]

Using this ensemble and notation, we can prove the following theorem:

Theorem 4.1. Let Pd be the probability that the transmitted digit in position d is a 1 conditional on the received digit in position d, and let Pil be the same probability for the lth digit in the ith parity-check set of the first tier in Figure 4.1. Let the digits be statistically independent of each other, and let S be the event that the transmitted digits satisfy the j parity-check constraints on digit d. Then

P2)Prx[d0y|{S},]Pd11l1(1il] [Pr[xd1|{y},S]Pdi11k1(12Pil)l1jk1

(4.1)

In order to prove this theorem, we need the following lemma:

Lemma 4.1. Consider a sequence of m independent binary digits in which the lth digit is a 1 with probability Pl . Then the probability that an even number of digits are 1 is

1l1(12Pl)

2m

Proof of the Lemma. Consider the function

(1PPt) ll

l1m

Observe that if this is expanded into a polynomial in t, the coefficient of ti is the probability of i 1’s. The function m

l1(1PlPtl) is identical except that all the odd

powers of t are negative. Adding these two functions, all the even powers of t are doubled, and the odd terms cancel out. Finally letting t = 1 and dividing by 2, the result is that the probability of an even number of ones.

But

l1(1PlPl)l1(1PlPl)

2

thus proving the lemma. mm1l1(12Pl)2m

Proof of the Theorem. By the definition of conditional probabilities

Pr[xd0|{y},S]1PdPr[xd1|{y},S]PdPr[xd0|{y}] (4.2) i1Pr[xd1|{y}]j

Given that xd=0, a parity check on d is satisfied if the other (k-1) positions in the parity-check set contain an even number of 1’s. Since all digits in the ensemble are statistically independent, the probability that all j parity-checks are satisfied is the product of the probabilities of the individual checks being satisfied. Using Lemma 4.1 this is

Pr[S|xd0,{y}][

i1j1l1(12Pil)2j] (4.3) Similarly,

Pr[S|xd1,{y}][

i1j1l1(12Pil)2j] (4.4)

Substituting Equations (4.3) and (4.4) into Equation (4.2) we get the statement of the theorem.

Judging from the complexity of this result, it would appear difficult to compute the probability that the transmitted digit in position d is a 1 conditional on the received digits

in two or more tiers of the tree in Figure 4.1. Fortunately, however, the many-tier case can be solved from the 1-tier case by a simple iterative technique.

Consider first the 2-tier case. We can use Theorem 4.1 to find the probability that each of the transmitted digits in the first tier of the tree is a 1 conditional on the received digits in the second tier. The only modification of the theorem is that the first product is taken over only j-1 terms, since the parity-check set containing digit d is not included. Now these probabilities can be used in Equation (4.1) to find the probability that the transmitted digit in position d is 1. The validity of the procedure follows immediately from the independence of the new values of Pil in the ensemble used in Theorem 4.1. By induction, this iteration process can be used to find the probability that the transmitted digit d is 1, given any number of tiers of distinct digits in the tree.

The general decoding procedure for the entire code may now be stated. For each digit and each combination of j-1 parity-check sets containing that digit, use Equation (4.1) to calculate the probability of a transmitted 1 conditional on the received symbols in the j-1 parity-check sets. Thus there are j different probabilities associated with each digit, each one omitting 1 parity-check set. Next these probabilities are used in Equation (4.1) to compute a second-order set of probabilities. The probability to be associated with one digit in the computation of another digit d is the probability found in the first iteration, omitting the parity-check set containing d. If the decoding is successful, then the probabilities associated with each digit approach 0 or 1 (depending on the transmitted digit) as the number of iterations is increased. The procedure is valid only for as many iteration as meet the independence assumption in Theorem 4.1. This assumption breaks down when the tree closes upon itself. Since each tier of the tree contains (j-1)(k-1) times more nodes than the previous tier, the independence assumption must break down while m is quite small for any code of reasonable block length. This lack of independence can be ignored, however, on the reasonable assumption that the dependencies have a relatively minor effect and tend to cancel each other out somewhat. Also, even if dependencies occur in the mth iteration, the first m-1 iterations have reduced the equivocation in each digit. Then we can consider the probabilities after the m-1 iterations to be a new received sequence that should be easier to decode than original received sequence.

The most significant feature of this decoding scheme is that the computation per digit per iteration is independent of the block length. Furthermore, it can be shown that the average number of iterations required to decode is bounded by a quantity proportional to the log of the log of the block length.

For the actual computation of the probabilities in Theorem 4.1, it appears to be more convenient to use Equation (4.1) in terms of log-likelihood ratios.

Let

ln

ln

ln1PdddPd1PilililPilPr[xd0|{y},S]'dd'Pr[xd1|{y},S] (4.5)

Where  is the sign and  is the magnitude of the log likelihood ratio. After some manipulation, Equation (4.1) becomes

dd(il)f[f(il)] (4.6) '

d'd

i1l1l1jk1k1

where

e1f()ln e1

The calculation of the log-likelihood ratios in Equation (4.6) for each digit can be performed either serially in time or by parallel computations. The serial computation can be programmed for a general-purpose computer, and the experimental data in Chapter 6 was obtained in this manner. For fast decoding, parallel computing is more promising, and Figure 4.2 sketches a simplified block diagram showing how this can be done.

If the input to the decoder is in the form of a log-likelihood ratio, the first row of boxes in Figure 4.2 computes f() for each digit, corresponding to the rightmost operation in Equation (4.6). The output from the adders on the next row is k1

l1f(il),

corresponding to the two rightmost operations in Equation (4.6). Likewise, successive rows in Figure 4.2 correspond to operations in Equation (4.6) working to the left. Clearly, Figure 4.2 omits some details, such as the operations on the signs of the log-likelihood ratios with each digit, but these create no essential difficulty.

We see from Figure 4.2 that a parallel computer can be simply instrumented requiring principally a number proportional to n of analogue adders, modulo 2 adders, amplifiers and nonlinear circuits to approximate the function f(). How closely this function must

approximated is a subject for further study, but there are indications that it is not critical.

Figure 4.2 : Decoding apparatus

4.1 简介

第三章分析了(n, j, k)码在各种二进制输入信道当中采用最大似然译码的错误译码概率。最大似然译码是一个方便的概念，因为它最大限度地减少了译码错误的概率，因此衡量了除其他任何特定译码方法外的一种码的有效性。但是，实施实际上用接受到的序列和所有可能的码相比较的最大似然译码是一种最没有吸引力的可能；这千真万确因为块长度很长，而码集合的大小随块长度呈指数增加。解码器，从设备，存储条件来看应该是相对简单的，并且算法较为可取，即使适度增加出错的概率。如果要求有更低的出错概率，人们只需要简单地增加码的块长度。

这里将描述在复杂度和译码错误概率之间寻求一个合理的平衡的两种译码方案。第一种特别简单，但是它只适用于码率远远低于其容量的二进制对称信道（BSC）。直接从信道输出的后验概率译码的第二种方案更加有前途，但是它在第一种方案被描述过之后才更容易理解。

在第一种译码方案中，译码器运算所有的奇偶校验，然后更改任何包含超过某些固定数目的未满足校验方程的数位。奇偶校验使用这些新值被重新运算，并且这个过程将被重复，直到所有的奇偶校验都被满足。

如果奇偶校验的集合较小，译码的过程是合理可行的，因为大多数奇偶校验集合只包含一个或者没有传输错误。因此，当大多数奇偶校验方程在校验一位时不满足，则很可能说明那一位出错了。举例来说，假设图2.1中的第一位发生了传输错误。那么，奇偶校验1，6和11将被破坏，上述三个奇偶校验等式在检测数位1的时候将被破坏。另一方面，至多三者中有一个等式在校验其他位时被破坏。

要想看到任意数位d是怎样被纠正的，即使它的奇偶校验集合包含了多于一个的传输错误，请考查如图4.1的树结构。树底部的节点代表数位d，每一条从这个节点发出的线代表一个包含数位d的奇偶校验集合。树的第一层的节点代表这些奇偶校验集合中的其他数位。从层1向层2发出的线代表其他奇偶校验集合包含的层1的数位，层2中的节点代表在那些集合中的其他数位。注意如果这样的树扩展到许多层，那么同一数位可能会出现在不用位置，这些将在4.2部分中予以探讨。

假设现在数位d和其他几个第一层的数位是传输错误。那么在第一次译码尝试中第二层中的无错数位和它们的奇偶校验约束将允许对第一层错误的改正。这反过

来在第二次译码尝试中将允许数位d的修正。因此，数位和奇偶校验方程可以帮助译码一个似乎和它们无关的数位。概率译码方案被描述成更系统的使用这些额外的数位和奇偶校验方程。

图4.1：奇偶校验集合树

4.2 概率译码

假设一个(n, j, k)码的码字在一个任意的二进制输入信道中被等概使用。对于任何数位d，使用如图4.1中的符号，一个迭代过程将被导出：在第m次迭代中计算在位置d的传输数位是1，前提条件是接受到的符号输出到并且包含第m层。就第一次迭代来说，我们可以考虑数位d和第一层的数位构成了一个“亚码”在满足树中j奇偶校验方程数位的集合中有传输的相等概率。

考虑在位置d的传输数位中的所有项和第一层是独立的等概率的二进制数位，并且在这些位置接收到的符号的概率被信道转移概率Px(y)决定。在这全体之中，任一项的概率的条件是传输数位满足j奇偶校验方程。而（这概率）是相同的，就像上述的“亚码”中一项一样。因此，在这个全集之中，我们想找到的是在位置d的传输数位是1的条件概率，这概率的条件是接受符号集合{y}和传输数位的项S在数位d满足j奇偶校验方程。我们这样写下：

Pr[xd1|{y},S]

用这个全体和符号，我们可以证明如下定理：

定理4.1 设Pd是传输数位在位置d是1且接收的数位是在位置d的条件概率，并且设Pil是图4.1第一层第i奇偶校验集合中第l位的同样的概率。设各数位彼此是统计独立的，且令S是传输数位在数位d满足j奇偶校验约束的项。那么

P2)Prx[d0y|{S},]Pd11l1(1il (4.1) []k1Pr[xd1|{y},S]Pdi11(12Pil)l1jk1

为了证明这个定理，我们需要如下引理：

引理 4.1 独立二进制序列m其中第l数位是1的概率是Pl。则包含偶数个1的概率是

1l1(12Pl)

2m

引理得证。考虑这个函数

(1PPt)ll

l1m

观察到如果它扩展成一个关于t的多项式，ti的系数为i是1的概率。

m

l1(1PlPtl)这个函数是相同的，除了所有t的奇数次幂都是负的。把这两个函数相加，所有的偶次幂被翻倍，所有的奇次幂消去。最终设t = 1并且除以2，结果是有偶数个1的概率。

但是

l1(1PlPl)l1(1PlPl)

2

这证明了引理。 mm1l1(12Pl)2 m

定理得证。由条件概率的定义

Pr[xd0|{y},S]1PdPr[xd1|{y},S]PdPr[xd0|{y}] (4.2) i1Pr[xd1|{y}]j

给定xd=0，如果奇偶校验集合其他(k-1)个位置上包含偶数个1，在d上的奇偶校验满足。因为全集中的所有的数位是统计独立的，所有j奇偶校验被满足的概率是每一个校验被满足的概率的乘积。采用引理4.1，即

Pr[S|xd0,{y}][

i1j1l1(12Pil)2j] (4.3)

相似地，

Pr[S|xd1,{y}][

i1j1l1(12Pil)2j] (4.4)

把(4.3) 式和(4.4)式代入(4.2)式中，我们得到定理的陈述。

从这一结果的复杂性上来看，似乎是难以计算转移数位在位置d上是1且收到的数位在图4.1的树中2层或更多的层上的条件概率。幸运的是，多层案例可以由一层案例用一个简单的迭代技术解决。

先考虑2层的情况。我们可以利用定理4.1找到该树第一层的每一传输数位是1且接受到的数位在第二层的条件概率。该定理的唯一修改是第一乘积被使用j-1次，因为校验位集合包含的数位d不包括在内。现在，这些概率可以用在(4.1)中，来求出传输数位在位置d是1的概率。该过程的正确性直接服从于定理4.1中使用的全体中的Pil的新值的独立性。通过归纳，这个迭代过程可以用来求解树中给定的任何不同层传输的数位d是1的概率。

对于整个码的一般译码过程现在可以加以说明。对于每一个数位和每一个包含该数位的j-1奇偶校验集合的组合而言，采用(4.1)式来计算传输1接收的符号在j-1奇偶校验集合中的条件概率。因此，有j个不用的概率和每一位相关联，每一个都省略了1奇偶校验集合。下一步这些概率是用在(4.1)式中来计算一个二阶概率集合。这个概率被关联于其他一个数位d是在第一次迭代中被求解出的概率的运算中的一个数位，忽略这个校验集合中含有的d。如果译码是成功的，则和每一位关联的概率接近0或1（取决于传输数位）同时迭代次数增加。这过程仅在很多迭代满足定理4.1中假设的独立性时才有效。如果此树闭合，这个假设失效。因为树中的每一层包含(j-1)(k-1)次比上一层更多的节点，当m对于任意合理块长度的码是相当小的时候，独立性假设必将被破坏。然而，在独立性有相对轻微影响并可以相互抵消的合理的假设中，这种独立性的缺陷可以被忽略。此外，即使独立性发生在第m次迭代中，前m-1次迭代也削减了每一数位的模糊度。那么，我们可以考虑m-1次迭代后的概率是一个新的接收序列，该序列比原接收序列更易于译码。

这个译码方案最重要的特点是，每数位每次迭代的运算和块长度是独立的。此外，它可以表明，平均的迭代次数要求译码和块长度对数的对数成正比约束。

对于定理4.1中关于概率的实际运算来说，在对数似然比方面运用(4.1)式更加方便。

设

ln

ln

ln1PdddPd1PilililPilPr[xd0|{y},S]'dd'Pr[xd1|{y},S] (4.5)

是记号，是对数似然比的大小。经过一些整理，(4.1)式变为

dd(il)f[f(il)] (4.6) '

d'd

i1l1l1jk1k1

这里

e1f()lne1

在(4.6)式中对每一数位的对数似然比的计算可以在时域上串行或者并行运算。串行计算可以被编程为一个通用计算机，第6章当中的实验数据就是通过这种方法获得的。为了快速译码，并行计算是更有前途的，图4.2描绘的简化框图显示了这是如何实现的。

如果译码器的输入是对数似然比的形式，则图4.2表格中的第一行计算了f(β)中的每一数位，对应于(4.6)式中最右面的操作。下一行的累加器中的输出是

，与(4.6)式中最右面两行的操作对应。同样，图4.2的成功行对应(4.6)式左边的操作。显然，图4.2省略了一些细节，比如对于每一个数位的对数似然比的记号的操作，但是这些没有产生实质性的困难。

从图4.2我们看到，一个并行计算机的仪器需求比较简单，主要是一个对n成正比的模拟加法器，模2加法器，放大器和非线性电路的近似函数f(β)。如何紧密合作，这一点必须近似函数是进一步研究的课题，但有迹象表明，它并不是关键性的。

图 4.2：译码装置