现代迭代编码理论：Richardson & Urbanke 的里程碑之作

4星 · 超过85%的资源需积分: 10 71 浏览量更新于2024-07-31 3 收藏 4.67MB PDF 举报

现代编码理论是由T. Richardson和R. Urbanke所著的一本书，该书聚焦于迭代通道编码的最新进展。它将这一领域与概率编码和图论编码等概念相联系。迭代解码技术最初由Gallager在1960年的博士论文中提出，但一度被遗忘。1993年，Berrou、Glavieux和Titimajshima通过Turbo码的形式重新发现并推广了这一概念。随后，在90年代中期，MacKay、McNeal、Sipser、Spielman以及Luby、Mitzenmacher、Shokrollahi、Spielman和Steman等人独立地发展了这一技术，其形式更接近Gallager最初的构想。书中详述了迭代编码方法如何深刻影响了编码理论和实际应用，特别是在通信领域。这些方法通过利用概率模型和图形表示，能够在复杂的数据传输环境中实现高效的错误纠正和信息传递。作者们在书中深入探讨了各种迭代算法的设计原理，如 belief propagation (BP) 和 message-passing algorithm，它们在诸如低密度 parity-check (LDPC) 和 turbo 码这样的现代编码系统中扮演着核心角色。这本书不仅提供了理论基础，还包含了丰富的实证研究和案例分析，帮助读者理解如何在实际通信系统中优化编码性能。此外，书中还讨论了迭代编码与机器学习的交叉，展示了如何利用深度学习和其他人工智能技术进一步提升编码效率。《现代编码理论》对于任何从事信息传输、信号处理或通信工程领域的专业人士来说都是一本不可或缺的参考资料，它不仅更新了编码理论的前沿知识，也为未来的研究和技术创新奠定了坚实的基础。对于想要深入了解迭代编码技术的读者来说，这是一次全面且深入的探索之旅。

2 introduction

ern coding oers an alternative way of solving the communications problem. Most

current wireless communications systems have already adopted modern coding.

Technically, our aim is focused on Shannon’s classical problem: we want to trans-

mit a message across a noisy channel so that the receiver can determine this message

with high probability despite the imperfections of the channel. We are interested in

low-complexity schemes that introduce little delay and allow reliable transmission

close to the ultimate limit, the Shannon capacity.

We start with a review of the communications problem (Section 1.2), we cover

some classical notions of codes (Sections 1.3, 1.4, 1.5, 1.7, and 1.8), and we review the

channel coding theorem (Section 1.6). Section 1.9 gives an outline of the modern

approach to coding. Finally, we close in Section 1.10 with a review of the notational

conventions and some useful facts.

§1.2. Communications Problem

Consider the following communications scenario – the point-to-point communica-

tions problem depicted in Figure 1.1. A source transmits its information (speech, au-

source

channel sink

Figure 1.1: Basic point-to-point communications problem.

dio, data, . . . ) via a noisy channel (phone line, optical link, wireless, storage medium,

. . . ) to a sink. We are interested in reliable transmission, i.e., we want to recreate

the transmitted information with as little distortion (number of wrong bits, mean

squared error distortion, . . . ) as possible at the sink.

In his seminal paper in 1948, Shannon formalized the communications problem

and showed that the point-to-point problem can be decomposed into two separate

problems as shown in Figure 1.2. First, a source encoder transforms the source into

a bit stream. Ideally, the source encoder removes all redundancy from the source

so that the resulting bit stream has the smallest possible number of bits while still

representing the source with enough accuracy. e channel encoder then processes

the bit stream to add redundancy. is redundancy is carefully chosen to combat

the noise that is introduced by the channel.

To be mathematically more precise: we model the output of the source as a

stochastic process. For example, we might represent text as the output of a Markov

chain, describing the local dependency structure of letter sequences. It is the task of

the source encoder to represent this output as eciently as possible (using as few bits

as possible) given a desired distortion. e distortion measure reects the “cost” of

deviating from the original source output. If the source emits points in R

it might

Preliminary version – October 18, 2007

communications problem 3

be natural to consider the squared Euclidean distance, whereas if the source emits

binary strings a more natural measure might be to count the number of positions in

which the source output and the word that can be reconstructed from the encoded

source dier. Shannon’s source coding theorem asserts that, for a given source and

distortion measure, there exists a minimum rate R = R(d)(bits per emitted source

symbol) which is necessary (and sucient) to describe this source with distortion

not exceeding d. e plot of this rate R as a function of the distortion d is usually

called the rate-distortion curve. In the second stage an appropriate amount of redun-

dancy is added to these source bits to protect them against the errors in the channel.

is process is called channel coding. roughout the book we model the channel as

a probabilistic mapping and we are typically interested in the average performance,

where the average is taken over all channel realizations. Shannon’s channel coding

theorem asserts the existence of a maximum rate (bits per channel use) at which in-

formation can be transmitted reliably, i.e., with vanishing probability of error, over

a given channel. is maximum rate is called the capacity of the channel and is de-

noted by C. At the receiver we rst decode the received bits to determine the trans-

mitted information. We then use the decoded bits to reconstruct the source at the

receiver. Shannon’s source-channel separation theorem asserts that the source can be

reconstructed with a distortion of at most d at the receiver if R(d)< C, i.e., if the

rate required to represent the given source with the allowed distortion is smaller

than the capacity of the channel. Conversely, no scheme can do better. One great

benet of the separation theorem is that a communications link can be used for a

large variety of sources: one good channel coding solution can be used with any

source. Virtually all systems in use today are based on this principle. It is important

channel

encoder

channel

decoder

source

encoder

source

decoder

source

sink

Figure 1.2: Basic point-to-point communications problem in view of the source-

channel separation theorem.

though to be aware of the limitations of the source-channel separation theorem. e

optimality is only in terms of the achievable distortion when large blocks of data are

encoded together. Joint schemes can be substantially better in terms of complexity

Preliminary version – October 18, 2007

4 introduction

or delay. Also, the separation is no longer valid if one looks at multi-user scenarios.

We will not be concerned with the source coding problem or, equivalently, we

assume that the source coding problem has been solved. For us, the source emits a

sequence of independent identically distributed (iid) bits which are equally likely to

be zero or one. Under this assumption, we will see how to accomplish the channel

coding problem in an ecient manner for a variety of scenarios.

§1.3. Coding: Trial and Error

How can we transmit information reliably over a noisy channel at a strictly positive

rate? At some level we have already given the answer: add redundancy to the message

that can be exploited to combat the distortion introduced by the channel. By starting

with a special case we want to clarify the key concepts.

1 − є

-1

Figure 1.4: BSC(є)

Example 1.3 (Binary Symmetric Channel). Consider the binary symmetric chan-

nel with cross-over probability є depicted in Figure 1.4. We denote it by BSC(є). Both

input X

and output Y

are elements of 1. A transmitted bit is either received

correctly or received ipped, the latter occurring with probability є, and dierent

bits are ipped or not ipped independently. We can assume that 0 < є <

without

loss of generality.

e BSC is the generic model of a binary-input memoryless channel in which

hard decisions are made at the front end of the receiver, i.e., where the received value

is quantized to two values. n

First Trial: Suppose that the transmitted bits are independent and that PX

+1= PX

= −1=

. We start by considering uncoded transmission over the

BSC(є). us, we send the source bits across the channel as is, without the insertion

of redundant bits. At the receiver we estimate the transmitted bit X based on the

observation Y. As we will learn in Section 1.5, the decision rule that minimizes the

bit-error probability, call it

MAP

(y), is to choose that x > 1which maximizes

X SY

(x Sy)for the given y. Since the prior on X is uniform, an application of Bayes

rule shows that this is equivalent to maximizing p

Y SX

(ySx)for the given y. Since

є <

we conclude that the optimal estimator is

MAP

(y)= y. e probability that the

Preliminary version – October 18, 2007

codes and ensembles 5

estimate diers from the true value, i.e., P

= P 

MAP

(Y)x X, is equal to є. Since

for every information bit we want to convey we send exactly one bit over the channel

we say that this scheme has rate 1. We conclude that with uncoded transmission we

can achieve a (rate, P

)-pair of (1, є).

Second Trial: If the error probability є is too high for our application, what trans-

mission strategy can we use to lower it? e simplest strategy is repetition-coding.

Assume we repeat each bit k times. To keep things simple, assume that k is odd. So

if X, the bit to be transmitted, has value x then the input to the BSC(є)is the k-tuple

x,  , x. Denote the k associated observations by Y

 Y

. It is intuitive, and not hard

to prove, that the estimator that minimizes the bit-error probability is given by the

majority rule

MAP

,  , y

)= majority of y

,  , y

.

Hence the probability of bit error is given by

= P



MAP

(Y)x X



k odd

= P



at least



k~2



errors occur



iAk~2



є

(1 − є)

k−i

Since for every information bit we want to convey we send k bits over the chan-

nel we say that such a scheme has rate

. So with repetition codes we can achieve

the (rate, P

)-pairs (

iAk~2





(1 − є)

k−i

). For P

to approach zero we have to

choose k larger and larger and as a consequence the rate approaches zero as well.

Can we keep the rate positive and still make the error probability go to zero?

§1.4. Codes and Ensembles

Information is inherently discrete. It is natural and convenient to use nite elds to

represent it. e most important instance for us is the binary eld F

, consisting of

0, 1with mod-2 addition and mod-2 multiplication (0 + 0 = 1 + 1 = 0; 0 + 1 = 1;

0 ċ 0 = 1 ċ 0 = 0; 1 ċ 1 = 1). In words, if we use F

then we represent information in

terms of (sequences of) bits, a natural representation and convenient for the purpose

of processing. If you are not familiar with nite elds, very little is lost if you replace

any mention of a generic nite eld F with F

. We write SF Sto indicate the number

of elements of the nite eld F, e.g., SF

S= 2. Why do we choose nite elds? As we

will see, this allows us to make use of algebraic operations in both the encoding as

well as the decoding, signicantly reducing the complexity.

Definition 1.5 (C ode). A code C of length n and cardinality M over a eld F is a

collection of M elements from F

, i.e.,

C(n, M)= x

[1]

,  , x

[M]

, x

[m]

> F

, 1 B m B M.

e elements of the code are called codewords. e parameter n is called the block-

length. S

Preliminary version – October 18, 2007

6 introduction

Example 1.6 (Repetition Code). Let F = F

. e binary repetition code is dened

as C(n = 3, M = 2)= 000, 111. n

In the above example we have introduced binary codes, i.e., codes whose com-

ponents are elements of F

= 0, 1. Some times it is more convenient to think of

the two eld elements as 1instead (see, e.g., the denition of the BSC in Ex-

ample 1.3). e standard mapping is 0  1 and 1  −1. It is convenient to use

both notations. We freely and frequently switch and, with some abuse of notation,

we make no distinction between these two cases and simply talk about binary codes

and F

even if the components take values in 1.

Definition 1.7 (Rate). e rate of a code C(n, M)is r =

log

SF S

M. It is measured

in information symbols per transmitted symbol. S

Example 1.8 (R epetition Code). Let F = F

. We have r(C(3, 2))=

log

2 =

It takes 3 channel symbols to transmit one information symbol. n

e following two denitions play a role only much later in the book. But it is

convenient to collect them here for reference.

Definition 1.9 (Support Set). e support set of a codeword x > C is the set of

locations i > [n]= 1,  , nsuch that x

x 0. S

Definition 1.10 (Minimal Codewords). Consider a binary code C, i.e., a code

over F

. We say that a codeword x > C is minimal if its support set does not contain

the support set of any other (non-zero) codeword. S

e Hamming distance introduced in the following denition and the derived

minimum distance of a code (see Denition 1.12) are the central characters in all of

classical coding. For us they only play a minor role. is is probably one of the most

distinguishing factors between classical and modern coding.

Definition 1.11 (Hamming Weight and Hamming Distance). Let u, v > F

. e

Hamming weight of a word u, which we denote by w(u), is equal to the number of

non-zero symbols in u, i.e., the cardinality of the support set. e Hamming distance

of a pair (u, v), which we denote by d(u, v), is the number of positions in which u

diers from v. We have d(u, v)= d(u− v, 0)= w(u − v). Further, d(u, v)= d(v, u)

and d(u, v)C 0, with equality if and only if u = v. Also, d(ċ, ċ)satises the triangle

inequality

d(u, v)B d(u, t)+ d(t, v),

for any triple u, v, t > F

. In words, d(ċ, ċ)is a true distance in the mathematical

sense (see Problem 1.2). S

Preliminary version – October 18, 2007

剩余589页未读，继续阅读

fanbird2008

粉丝: 208
资源: 249

现代迭代编码理论：Richardson & Urbanke 的里程碑之作

modern coding theory

Modern coding theory（Tom Richardson）习题答案

Modern Coding Theory

Distributed.Source.Coding.Theory.and.Practice.epub

Introduction to modern coding theory.pdf

modern-coding-theory.rar_matlab例程_MultiPlatform_

Secure.Coding.in.C.and.Cplusplus.2nd.Edition.0321822137.epub

SUMS14 Information and Coding Theory, Gareth A. Jones

Error control coding. From theory to practice.Sweeney P. (Wiley,2002)

SUMS14 Information and Coding Theory, Gareth A. Jones, J. Mary Jones (2000) .zip

最新资源