Branching Process Techniques
We first briefly review the elementary theory of branching processes and then develop the kind of generalization required here. Let Mn be the total number of particles at time n and let xj,n be the number of particles that the jth of these Mn particles sp
- PDF / 6,522,940 Bytes
- 116 Pages / 481.879 x 691.645 pts Page_size
- 96 Downloads / 228 Views
ROBERT GALLAGER MASSACHUSETTS INSTITUTE OF TECHNOLOGY, CAMBRIDGE
INFORMATION THEORY AND RELIABLE COMMUNICATION
COURSE HELD AT THE DEPARTMENT OF AUTOMATION AND INFORMATION JULY 1970
UDINE 1970
SPRINGER-VERLAG WIEN GMBH
This work is subject to copyright.
AII rights are reserved, whether the whole or part of the material is concemed specifically thc.se of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks.
©
1972 by Springer-Verlag Wien
Originally published by Springer-Verlag Wien-New York in 1972
ISBN 978-3-211-81145-0 DOI 10.1007/978-3-7091-2945-6
ISBN 978-3-7091-2945-6 (eBook)
PREFACE
The following notes were developed by the author in July 1970 in a aourse on Information Theory at the "Centro Internazionale di Saienze Meaaaniahe". Exaept for seation 4, whiah developes a new theory of random trees, most of the material is to be found in expanded form in the author's book, "Information TheoPy and Reliable Communiaation",John Wiley and Sons, New York, l968. A numbeP of the results have been proved here in more satisfying ways whiah have been developed sinae the publiaation of the book. A higher level of mathematiaal maturity has been assumed here than in the book and an attempt has been made to present some of the deeper aspeats of the subjeat with out so muah introduatory material. The author would like to express his appreaiation to Professor Giuseppe Longo, who organized this set of aourses, and to Professor Luigi Sobrero, the Searetary General of C.I.S.M., for their hospitality and for making this work possible.
4
Preface
Finally, he is grateful to the students in the course whose interest and enthusiasm made this a stimulating endeavor.
Robert G. Gallager (Prof. of E.E., Mass.Inst. of Tech., U.S.A.) Udine, Italy, July 10, 19?0.
PART
I
Introduction
In these notes we shall deal with a number of problems that at first glance seem somewhat disparate. First we shall deal with the noisy channel coding theorem, particularly as related to channels somewhat more complicated than the usual discrete memoryless channel. Then we shall deal with the source coding theorem for sources with a distortion measure defined on them. Finally we shall present some new results on a class of processes called random trees and apply these results to the theory of convolutional codes. Before going into any of the technical details of these topics, however, it will be appropriate to try to give some engineering perspective into how these topics fit together and how they relate to the problems of communication. In Fig. 1. 1 we show the traditional block diagram of a communication system. The encoder and decoder there are not to be thought of necessarily as the traditional kind of block codes and decoders but rather as any kind of data processing which is included to make the communication more effective. One of the key distinguishing characteristics of information theory which distinguishes it from the older theories of optim
Data Loading...
