Thisbookismainlyabouttheoreticalfoundationsofinformationtheoryandcoding.Also,somepracticalapplicationsofthesetheoriesarementionedinsomeoccasions.Onthebasisofintroducingmeasuresofinformation,itmainlyfocusesontheintroductionofthetheoryoflosslesssourcecoding,limitedlosssourcecoding,channelcodingandtheirapplications.Inaddition,itpaysattentiontobasicconceptsandusespopulartextstoexplainthem.

Preface
The information theory is mathematical theory of communication theory. It is science
to study information measures and coding by using mathematical statistics method. It can
be divided into generalized information theory and narrow information theory which is
also called classical theory of information or probabilistic information theory.
This book is on the foundation of probabilistic information measures and their
application of coding theorems for information sources and noisy channels. It pays
attention to elaborate the basic theories, concepts and methods. With this idea, there are
many examples throughout this book which will make these concepts and theorems clearer
and easier understanding. A mathematical book has the potential danger of scaring away
beginners. Therefore, We make every effort to use simple mathematics tools in the
argument of information theory, which may help beginners on the way of mastering it.
It can be used as teaching material in Electronics Department for college students of
upper grade or for graduate students. The whole book is composed of five chapters. which
are both lively introduced and attached by the detail references of the fascinating world of
information theory.
Chapter 1 is introduction, it’s the outline about the basic problems of information
theory and coding from the angle of history. For example, the concept of information and
measures it takes, the formation and development of information theory, and so on.
Chapter 2 deals with some basic concepts on information measurement. Through the
study of this chapter you may gain the ability of knowing how much information you can
get from a trial of tossing a coin and read the result of it. Also, this chapter introduces some
theorems on continuous source and discrete source.
Chapter 3 deals with lossless source coding theorems. In chapter 3, you will know
that source which needs compressed to suit for the transmission. In this part, it answers
how to compress the information of source kept.
Chapter 4 deals with limited distortion source coding. Former chapters are all under
the condition of lossless distortion, but in real world, to a certain degree distortion can’t be
avoided by people, for the information in transmission and records can be more or less.
This chapter is about the theorems and practice based on this idea.
Chapter 5 is about channel. For channel, it uses channel capacity to measure the
transfer ability. The channel model and the capacity calculation of some typical channels
discrete or continuous ones are the focus. It also introduces the coding theory. Some
famous and useful coding methods are included in it, such as CRC code, and Hamming
PREFACE
2 信
息
论
与
编
码
(
英文版)
code, etc. After the study of this part, readers can see the real situation of information
transmission.
The contents of this book is from simple to complex. To improve the ability of
analyzing and solving problems, there are some questions and exercises attached at the end
of each chapter.
This book is the harvest of hard work and wisdom of a group of people. The members
participating the writing of the book are Liang Jianwu (Chapter1-3), Luo Xiying (from
Human University of Science and Technology, Chapter 4), Guo Ying (Chapter 5). Fu
Liaoyan, the English department dean of Changsha medical college, is the master auditor
of this book. Besides, Liu Junjun, Long Xiaomei, Tian Ye, Zhou Yuanyuan, He Zhibin, Li
Huawei, Fu Shifeng, Tan Hailong, Wen Zheng, did great favors for the writing of this book.
We have tried our best to free it from all errors. Unfortunately there does not exist a
foolproof error control technique for that. Therefore, you are welcome to point out our
mistakes and give us your opinions.
Authors of this book in Central South University
2015-03-18

目 录
Chapter 1 Introduction ............................................................................................ 1
Before it starts, there is something must be known ........................................... 1
1.1 What is Information .................................................................................... 2
1.2 What is Information Theory ....................................................................... 4
1.2.1 The Origin and Development of Information Theory ....................... 4
1.2.2 The Application and Achievement of Information Theory
Methods ............................................................................................. 6
1.3 Formation and Development of Information Theory ............................... 8
Questions and Exercises ....................................................................................... 8
Biography of Claude Elwood Shannon ............................................................... 8
Chapter 2 Basic Concepts of Information Theory ........................................ 11
Preparation knowledge ........................................................................................ 11
2.1 Self-information and conditional self-information ................................. 13
2.1.1 Self-information .............................................................................. 13
2.1.2 Conditional Self-information .......................................................... 14
2.2 Mutual information and conditional mutual information ..................... 14
2.3 Source entropy ............................................................................................ 16
2.3.1 Introduction of entropy .................................................................... 16
2.3.2 Mathematics description of source entropy .................................... 17
2.3.3 Conditional entropy ......................................................................... 20
2.3.4 Union entropy .................................................................................. 20
2.3.5 Basic nature and theorem of source entropy ................................... 21
2.4 Average mutual information ..................................................................... 26
2.4.1 Definition ......................................................................................... 26
2.4.2 Physics significance of average mutual information ...................... 27
2.4.3 Properties of average mutual information ....................................... 28
2.5 Continuous source ...................................................................................... 37
2.5.1 Entropy of the continuous source .................................................... 37
2.5.2 Mutual information of the continuous random variable ................. 42
CONTENTS
2 信
息
论
与
编
码
(
英文版)
2.6 Multi-marks discrete steady source ......................................................... 43
2.6.1 Mathematical model and classification of the source ..................... 43
2.6.2 The discrete source without memory .............................................. 46
2.6.3 Multi-marks discrete steady source ................................................. 51
2.6.4 Source entropy of discrete steady source and limit entropy ........... 58
2.6.5 The source redundancy and the information difference .................. 63
2.6.6 Markov information source ............................................................. 63
Chapter 3 Lossless source coding ................................................................... 77
3.1 Lossless coder ............................................................................................. 77
3.2 Lossless source coding ............................................................................... 81
3.2.1 Fixed length coding theorem ........................................................... 81
3.2.2 Unfixed length source coding ......................................................... 85
3.3 Lossless source coding theorems ............................................................... 87
3.3.1 Classification of code and main coding method ............................. 87
3.3.2 Kraft theorem .................................................................................. 87
3.3.3 Lossless unfixed source coding theorem ......................................... 88
3.4 Pragmatic examples of lossless source coding ......................................... 91
3.4.1 Huffman coding ............................................................................... 91
3.4.2 Shannon coding and Fano coding ................................................... 98
3.5 The Lempel-ziv algorithm ....................................................................... 100
3.6 Run length encoding and the PCX format ............................................ 102
Chapter 4 Limited distortion source coding ................................................. 107
4.1 The start point of limit distortion theory ............................................... 108
4.2 Distortion measurement ........................................................................... 110
4.2.1 Distortion function ......................................................................... 110
4.2.2 Average distortion .......................................................................... 112
4.3 Information rate distortion function ....................................................... 113
4.4 Properties of R(D) ................................................................................... 115
4.4.1 Minimum of D and R(D) .............................................................. 115
4.4.2 Dmax and R(Dmax) ......................................................................... 121
4.4.3 The under convex feature of R(D) ............................................... 124
4.4.4 The decreasing feature of R(D) ................................................... 124
4.4.5 R(D) is a continuous function of D ............................................... 124
4.5 Calculation of R (D) ............................................................................... 126
4.5.1 Calculation of R(D) of binary symmetric source .......................... 126
4.5.2 Calculation of R(D) of Gauss source ............................................ 128
4.6 Limited distortion source encoding theorem ......................................... 129
3
目录
Chapter 5 Channel Capacity and Channel Coding ................................... 140
5.1 The model and classification of the channel .......................................... 140
5.1.1 Channel Models ............................................................................. 140
5.1.2 Channel classifications .................................................................. 142
5.2 Channel doubt degree and average mutual information ..................... 143
5.2.1 Channel doubt degree .................................................................... 143
5.2.2 Average mutual information .......................................................... 143
5.2.3 Properties of mutual information function .................................... 144
5.2.4 Relationships among entropy, channel doubt degree and
mutual information ........................................................................ 147
5.3 Channel capacity ...................................................................................... 148
5.3.1 Concept of channel capacity ......................................................... 148
5.3.2 Discrete channel without memory and its channel
capacity .......................................................................................... 149
5.3.3 Continuous channel and its channel capacity ............................... 159
5.4 Channel coding theorem .......................................................................... 162
5.4.1 Channel coding theorem for noisy channel ................................... 162
5.4.2 Introduction: The generator and parity-check matrices ................ 165
5.4.3 Error control .................................................................................. 168
5.4.4 Optimal decoding and maximum likelihood decoding ................. 169
5.5 Syndrome decoding on q-ary symmetric channels ............................... 172
5.6 Error correction coding ........................................................................... 174
5.6.1 Hamming geometry and code performance .................................. 174
5.6.2 Hamming code ............................................................................... 177
5.6.3 Cyclic code .................................................................................... 179
5.7 Convolutional codes ................................................................................. 189
5.7.1 Basic concepts and describing methods ........................................ 189
5.7.2 Maximum likelihood decoding of convolutional code ................. 192
5.7.3 Convolutional codes performance limit and distance
characteristics ................................................................................ 194
5.8 Syndrome decoding on general q-ary channels ..................................... 195
Bibliography .............................................................................................................. 204

梁建武：男，中共党员，副高。就职于中南大学。承担本科教学6门、研究生教学1门、参加国家自然科学基金一项，省基金2项,工程项目10余项,编写教材6本（十一五国家教材一本）。罗喜英：博士，副教授，现就职于湖南科技大学，专业方向为信息理论，主讲课程：信息论与编码。郭迎：博士，教授，现就职于中南大学，专业方向为通信工程。