低密度奇偶校验检查码：实现高效通信

需积分: 50 117 浏览量更新于2024-07-20 收藏 1.12MB PDF 举报

"Low-Density Parity-Check Codes - Robert G. Gallagher - 1963" Low-Density Parity-Check (LDPC) codes是由Robert G. Gallagher在1963年的博士论文中首次提出的，这是一类重要的纠错编码技术。它们在通信系统和数据存储中扮演着至关重要的角色，因为它们能够有效地对抗信道噪声，同时保持较高的数据传输速率。 Shannon在1948年提出了信息论中的噪声通道编码定理，它揭示了在存在噪声的通信通道中，通过使用适当的编码可以将错误率降低到几乎可忽略不计的程度，而不会牺牲数据速率。然而，理论的实用化一直受到实现复杂性和计算时间的限制。Gallager的贡献在于他提出了一种技术，即LDPC码，这种技术能够在保持高数据速率的同时，以相对较低的硬件复杂度和解码时间实现接近无误传输。 LDPC码的主要特点在于其稀疏的校验矩阵，这个矩阵中大多数元素都是零，只有少数是非零元素。这种低密度使得在解码过程中可以利用图论中的近似算法，如消息传递算法（Message Passing Algorithm, MPA），如Belief Propagation，大大降低了计算复杂性。相比于其他纠错编码，如Turbo码和Reed-Solomon码，LDPC码的解码效率更高，而且在大规模系统中更具优势。尽管LDPC码有这些优点，但其性能和适用性还是取决于具体的应用场景和信道条件。例如，在长距离光纤通信、卫星通信、无线通信以及硬盘存储等领域，LDPC码都得到了广泛应用。然而，与其他编码方案相比，其优缺点并不总是明显，因为这依赖于对错误纠正性能、实现复杂性、功耗和实时性的综合权衡。在实际应用中，LDPC码的设计通常涉及两个关键步骤：码构造和解码算法设计。码构造的目标是找到具有最优性能的校验矩阵，而解码算法则需要在保证正确性的同时尽量减少计算复杂性和延迟。随着研究的深入，各种优化的编码结构和改进的解码算法不断出现，如迭代软输入软输出（Soft-Input Soft-Output, SISO）解码算法，进一步提升了LDPC码的性能。 Low-Density Parity-Check Codes作为现代通信和数据存储领域的重要工具，其高效、灵活的特性使其成为对抗信道噪声的有效手段，持续推动着信息传输技术的发展。

Figure 2.2: The functions £/n and [\n N i(£ )]/n as parametric functions of s.

by assigning the same probability to each. The total number of sequences in

the ensemble is 2fc_1, and the probability of a sequence containing % ones (i

even) is (” 2 -fc+1. The moment-generating function for the number of ones in

a sequence is thus

g(s) = fc+1esi (2.10)

i even 、 ^

g(s) = 2_k [(1 + es)k + (1 — es)k] (2.11)

To show that Equations (2.10) and (2.11) are equivalent, use the binomial ex

pansion on Equation (2.11) and observe that odd terms cancel.

For each of the n /k parity-check sets, independently choose a sequence from

the previous ensemble and use that sequence as the binits in that parity-check

set. This procedure defines an ensemble of equiprobable events in which the

events are the n-length sequences satisfying the n /k parity checks. The number

of ones in an n-length sequence is the sum of the number of ones in the individual

parity-check sets, and thus the sum of n /k independent random variables each

having the moment-generating function g(s) in Equation (2.11). Consequently,

the moment generating function for the number of ones in an n-length sequence

is [g(s)}n^k. This is now used to bound the probability Q(£) in this ensemble

that a sequence has £ ones. By definition,

b (s) F = D exP (O Q W (2-12)

i=0

> exp(s£)Q(£)] for any s and £ (2.13)

From Equation (2.9) and Equation (2.11), fx(s) = \ng(s), so that

Q (l) < e x p ^fx(s ) — si]

Finally, N i(£) equals Q(£) times the number of sequences in the ensemble. Since

there are 2fc—1 sequences in the fc-length ensemble, there are 2n^ l ^ k sequences

in the n-length ensemble, so that

N ±{e) < exp -^ (^ ) + - ( f c - l ) l n 2 - ^ (2.14)

L K fC J

When we set the derivative of the exponent in Equation (2.14) equal to 0, we

get £ = and when we substitute this value of £ in Equation (2.14),

Equation (2.8) results, thereby proving the theorem. □

It is shown in Reference [4] that setting £ = [n ! K ) { s ) actually minimizes

the exponent, thereby yielding the best bound; however, the theorem is true

regardless of the minimal character of the exponent. Although it is not necessary

in the proof, it can be shown, using “tilted，，probabilities [4] and a central lim it

theorem [7], that asymptotically for large n,

Ni. [|^ ( « ) ]

丌二,⑷

exP | [^(« )—

叫

,W + ( * - 1 ) In 2] (2.15)

Theorem 2.3 can now be used to find the probability P(£) of the set of

codes for which some particular sequence of weight £ is a code word. Since

all permutations of a code are equally likely, P(£) is clearly independent of

the particular ^-weight sequence chosen. If we choose an ^-weight sequence at

random, then for any code in the ensemble the probability is N i (£) / (^) that the

weight sequence chosen will satisfy any particular block of n /k parity checks.

Since each of the j blocks of parity checks is chosen independently,

p m

(?)

(2.16)

The distance properties and the minimum-distance distribution function can

now be derived in terms of P(£) in the same way as they were derived for the

ensemble of all parity-check codes in Equations (2.1) and (2.5).

Njk w < m

n8 , \ n / \ —i +1

Pr(D < n S )< ^ Qj P(£) = h ^ (£y

Note that in the low-density ensemble only sequences of even weight

code words. Using Equations (2.4) and (2.14), we get

N jk(i) < C(A,n) exp —nB jk(X)] where A = —

^ jk (A) = ( j — l)H ( X ) —

臺

[fi(s) + (k — 1) In 2] + jsX

j — 1 rt

1 11^ ( Si

C(A,n) = [27rnA(l — A)] 2 exp

-----

— where A = ~ —

— AJ K

(2.17)

(2.18)

may be

(2.19)

(2.20)

(2.21)

The expression Sjk will be called the typical minimum-distance ratio of an

(n, j, k) ensemble. For large n, most codes in the ensemble have a minimum

distance either close to or greater than nSjk] since Sjk is independent of block

length, the minimum distance typical of most codes in the ensemble increases

linearly with the block length. Figure 2.4 plots Sjk as a function of rate for

several values of j and k and compares them w ith the typical minimum distance

ratio of the equiprobable ensemble of codes. It can be seen that as j and k

increases, Sjk for the (n, j, k) codes quickly approaches Sq for the equiprobable

ensemble of codes. This is proved in Theorem A .3 of Appendix A.

Sjk = Minimum distance ratio

Figure 2.4: Ratio of minimum distance to block length for typical long (n ，j ，k)

codes.

Here we see why a minimum-distance distribution function was derived be

fore any results were obtained about probability of decoding error. If two words

in a group code differ only in two digits, then the probability of a decoding error

is lower bounded by the probability of receiving those two digits incorrectly; this

is independent of code length. Thus, over the whole ensemble, the probability

of decoding error as n oo is proportional to l/ n J—2, the probability of codes

of minimum distance 2. Thus a very small number of poor codes dominates the

probability of decoding error over the ensemble.

In order to determine the probability of error behavior of typical (n, j, k)

codes with minimum distances in the order of nSjk, we shall modify the (n, j, k)

ensemble. Remove the half of the codes with smallest minimum distances from

an (n, j, k) ensemble and double the probability of each code in the remaining

half. The resulting ensemble will be called an expurgated (n, j, k) ensemble and

will be used in Chapter 3 to derive bounds on the probability of decoding error

for (n, j,fc) codes.

Let 5njk be the minimum distance of the expurgated ensemble. Then 5njk is

lower bounded by that value of 5 for which the right hand side of Equation (2.23)

is one-half. W ith increasing n, the bound of Equation (2.23) approaches a

剩余89页未读，继续阅读

xiongxhzju

粉丝: 0
资源: 12

低密度奇偶校验检查码：实现高效通信

Low Density Parity Check Codes

low-density-parity-check

matlab开发-来自ldpcParityCheckMatrix的编码消息

Improved Low-Density Parity-Check Codes Using Irregular Graphs

Serially concatenated belief propagation decoder for low-density parity-check codes

Design of low-density parity-check codes for modulation and detection.pdf

Low-density parity-check codes constructed from protographs

Iterative Error Correction Turbo, Low-Density Parity-Check

Introducing_Low-Density_Parity-Check_Codes

ldpc_distr_matlab_Low Density Parity-check Codes

最新资源