编码理论数学基础：信息处理与噪声编码解码

需积分: 7 195 浏览量更新于2024-07-24 收藏 13.43MB PDF 举报

《编码理论的数学》是一本深入浅出的教材，专为希望学习信道编解码理论的学生设计，特别是对那些需要理解其背后的数学原理的人。本书由Paul Garrett撰写，版权归属于Pearson Education（2004年）和Prentice-Hall，享有版权。书中内容涵盖了编码理论的核心概念，包括概率论、信息论、噪声编码和解码、以及循环冗余检查（CRC）等关键技术。在第一章“概率”中，作者首先介绍集合和函数的基本概念，然后探讨概率的两种观点：非正式的直观理解与更形式化的定义。接着，讨论了随机变量、期望值和方差，以及Markov不等式和Chebyshev不等式，这些都是理解信道编码性能的基础。随后的“大数定律”部分进一步阐述了在大量观察中的稳定性和预测性。第二章“信息”重点关注不确定性与信息获取，包括熵的概念，这是衡量信息量的关键度量。这部分对于量化信息传输效率至关重要。第三章“噪声less编码”深入研究了如何在没有噪声干扰的环境中编码信息，探讨了 Kraft-McMillan 不等式，以及噪声less编码定理，如著名的霍夫曼编码，它利用最优编码来减少信息的存储和传输成本。第四章转向“Noisy Coding”，即在存在噪声的通信环境中编码和解码技术。章节中通过实例，如“派对彩纸”的例子，来解释如何处理错误。此外，还介绍了从有噪声通道解码的方法，以及信道容量的概念，它是衡量信道传输最大数据速率的极限。第五章“Cyclic Redundancy Checks (CRCs)”专门探讨了基于二进制有限域GF(2)的编码技术，包括多项式运算在CRC设计中的应用。这部分着重说明CRC如何检测并纠正常见的错误类型，并解释了它能捕获什么样的错误。第六章“整数”可能涉及离散数学中的基础知识，这些内容可能是前几章理论应用的桥梁，例如在有限域和实际数字编码中的作用。《编码理论的数学》是一本全面的教育资源，将复杂的数学理论与实际的通信问题紧密结合，为学习者提供了一个坚实的数学基础，以便他们在信道编码和解码的实践中取得成功。通过系统地掌握这些内容，读者能够深入理解信道编解码技术在现代通信系统中的核心地位。

Chapter

1 Probability

This identity shows

that

the

binomial coefficients are integers,

and

the

basis for

other identities as well. This identity is proven by induction, as follows. For n

= 1

the assertion is immediately verified. Assume

true

for exponent

and

prove

the

corresponding assertion for exponent n +

Thus,

= t

(~)

(xk+1yn-k

xkyn-k+l)

k=O

xOyn+l

xn+lyO

+ + t

((k:

(~))

yn+l-k

k=l

Thus,

prove

the

formula of the Binomial Theorem for exponent n + 1

must

prove

that

for 1

We do

this

by expressing

the

left-hand side

terms of binomial coefficients:

n! n! n!

k n! (n - k + 1)

= + = + -:-;--::=-----:-----:--c-:

(k - I)! (n - k + I)!

(n - k)!

(n - k + I)!

(n+l)!

(n+l)

(n - k + I)! = k

as claimed.

1.3 Preliminary ideas

probability

This little section moves from

intuitive version

probability toward a more

formal

and

mathematically useful version presented in

the

next section.

First, there

the

conversion from

the

colloquial notion of

the

'chance'

something occurring

the

notion

its

'probability'. While usually

the

'chance'

something happening is a percentage, a

probability

is a number between 0

and

inclusive.

The

conversion rule is

the

following: if

colloquial English

the

'chance'

something happening is x%,

then

its

probability

x/tOO. (This introduces no

new content.) At one extreme, if

event is 'sure' to happen,

then

its probability

is 1 (its chance

100%), while

the

other

extreme

something is sure

not

happen

then

its probability is 0 (its chance

0%).

One basic postulate

about

probability is

that

the

probabilities

all

the

differ-

ent possible outcomes

event

experiment should

add

analogous

1.3 Preliminary ideas of probability

rule is taken as

true

for 'chance':

the

sum

the

percenta.ges of all possible outcomes

should be

100%.

But

what is 'probability'?

Example:

A 'fair coin' is presumed

have equal probabilities ('equal chances')

of landing heads-up or tails-up.

Since

the

probability of heads is

the

same as the

probability of tails,

and

since

the

two numbers should

add

1, there

choice

but

assign

the

probability

1/2

both. Further, each toss of

the

coin

presumed to-have

outcome independent of other tosses before

and

after.

That

is,

there

no mechanism by which

the

outcome of one toss affects another.

Now

come

a property which

would assume

be roughly true: out of (for example)

coin tosses

expect

about

half

be heads

and

about

half

be tails.

expect

that

would very seldom happen

that

out

tosses would all be

heads. Experience does

bear

this out. So far,

this vague language, there

obvious problem.

But, for example,

would be a mistake

too

aggressive, and say

that

should expect exactly half heads

and

half tails. Experimentation will show

that

out

of repeated batches of 10 coin flips, only about

1/4

the

time will there be exactly

5 heads

and

5 tails. (Only once

about

= 1024 times will one get all heads.)

fact,

about

2/5

the

time there will be either 6 heads

and

4 tails, or vice versa.

That

is, a 6-4 or 4-6 distribution of outcomes is more likely

than

the

'expected' 5-5.

But

this is not a paradox, since· upon reflection

our

intuition might assure us

not

that

there will be exactly half heads and half tails,

but

only approximately half

and half. And

can retell

the

story in a

better

way as follows.

what does

'approximately' mean, exactly?

In a

trial

of n coin flips, each flip has two possible outcomes, so there are

possible sequences of

n outcomes.

The

assumptions

that

the

coin is 'fair' and

that

the

separate coin tosses do not 'influence' each other is interpreted as saying

that

each one

the 2

possible sequences

coin-toss outcomes is equally likely.

Therefore,

the

probability of any single sequence of n outcomes is

1/2n.

Further,

for any subset

S of

the

set A of all 2

possible sequences of outcomes,

assume

that

probability of a sequence of n tosses giving an outcome in S

number of elements in S

number of elements in A

number of elements

Then

the

probability

that

exactly k heads will occur out of n tosses (with

0:$ k

n) is computed as

probability of

k heads

out

of n tosses

number of sequences of

n heads/tails with exactly k heads

total

number of sequences of n heads/tails

Chapter

1 Probability

flips and

approximate

the

probability, how many do

need

do? Third, how

know

that

every infinite sequence of trials will give

the

same limiting value?

There are many further objections

this as a fundamental definition,

but

should

be aware of interpretations in this direction. A more supportable viewpoint would

make such limiting frequency assertions a

consequence of

other

things, called

the

Law

Large Numbers. We'll prove a special case of this a

bit

later.

Example:

The

traditional example involves picking colored balls

out

urn. Suppose, for example,

that

there are N balls in

the

urn, r red ones

and

b = N - r blue ones,

and

that

they are indistinguishable by texture, weight, size,

or in any

way.

Then

in choosing a single ball from

the

urn

are 'equally likely'

choose

anyone

the

simpler case of coin flips, there are N

possibilities each

which is equally likely,

and

the

probabilities must

add

the

probability of drawing any particular ball

must

be 1

IN.

Further,

may seem

reasonable

postulate

that

the

probability of picking

out

one ball from among a

fixed subset of

k would be k times

the

probability of picking a single ball. Granting

this, with r red balls and

b blue ones,

would plausibly say

that

the

probability

is r

that

a red ball will

"chosen

and

biN

that

a blue ball will be chosen. (We

should keep

iI;l

mind

that

some subatomic particles do

not

behave in this seemingly

reasonable manner!)

So without assigning meaning

probability, in some cases

can still reach some conclusions

about

how

compute it.

We suppose

that

one draw (with replacement) has no effect on

the

next one,

that

they are

independent.

Let

r(n)

the number of red balls drawn in a

sequence of

n trials. Then, in parallel with

the

discussion

just

above,

would

presume

that

for any infinite sequence

trials

number of red balls drawn in

n draws

lim

n-+oo

But,

as noted above, this should

not

the

definition,

but

rather

should be a

deducible

consequence of whatever definition

make.

Running this. in

the

opposite direction: if there are N balls in

urn, some

red

and

some blue, if

r(n)

denotes

the

number of red balls chosen in n trials,

and

lim

r(n)

= f

n--+oo

then

would suspect

that

number of red balls in

the

urn

f . N

And

would suspect

that

the

probability of drawing a red ball in a single

trial

since

the

limiting frequency of drawing red balls is f.

But

how close would this equality be?

The

numbers above show

that

it is

not

very likely

that

a fair coin will give exactly half heads

out

of any number of flips,

so would

always fail

realize

that

had

a fair coin? Hmmm.

Again, yes,

the

limiting frequency intuition for probability is accurate,

but

isn't

adequate as a definition.

give a less intuitive definition in

the

next section,

and

later

return

limiting frequencies with

the

Law

Large Numbers.

剩余405页未读，继续阅读

海边拾趣

粉丝: 6
资源: 14

编码理论数学基础：信息处理与噪声编码解码

《入门代数数论：为高级本科生和研究生打下基础》

"常用级数求和方法详解与示例分析

"再思结构平衡：2019期刊中的发现与探讨

The mathematics of Coding theory _ Paul Garrett

the Mathematics of Gambling

Applications of Finite Geometry in Coding Theory and Cryptography-计算机科学

SUMS14 Information and Coding Theory

SUMS14 Information and Coding Theory, Gareth A. Jones

Mathematics in Computing

Graph Theory

最新资源