现代编码理论

This book is all about iterative channel decoding.Two other names which are often used to identify the same area are probabilistic coding and codes on graphs.Itera-tive decoding was originally conceived by Gallager in his remarkable Ph.D.thesis of 1960.Gallager's work was，evidently，far ahead of its time.Limitations in com-putational resources in the 1960 were such that the power of his approach could not be fully demonstrated，let alone developed.Consequently，iterative decoding at-tracted only passing interest and slipped into a long dormancy.It was rediscovered by Berrou，Glavieux，and Thitimajshima in 1993 in the form of turbo codes，and then independently in the mid iggos by MacKay and Neal，Sipser and Spielman，as well as Luby，Mitzenmacher，Shokrollahi，Spielman，and Stemann in a form much closer to Gallager's original construction.Iterative techniques have subsequently had a strong impact on coding theory and practice and，more generally，on the whole of commu-nications.The title Modern Coding Theory is clearly a hyperbole.There have been several other important recent developments in coding theory.To mention one prominent example： Sudan's algorithm and the Guruswami-Sudan improvement for list de-coding of Reed-Solomon codes and their extension to soft-decision decoding have sparked new life into this otherwise mature subject.So what is our excuse? Iter-ative methods and their theory are strongly tied to advances in current comput-ing technology and they are therefore inherently modern.They have also brought about a break with the past.Moreover，the techniques are influencing a wide range of applications within and beyond communications，connecting that area with many modern topics in，among others，statistical mechanics and complexity theory.Nev-ertheless，the font on the book cover expresses the irony that the roots of "modern"coding go back to a time when typewriters ruled the world.The field ofiterative decoding has not settled in the same way that classical cod-ing has.There are nearly as many flavors ofiterative decoding systems-and graphi-cal models to represent them-as there are researchers in the field.We have therefore decided to focus more on techniques to analyze and design such systems rather than on specific instances.In order to present the theory，we have elected Gallager's orig-inal ensemble oflow-density parity~check (LDPC) codes as a representative exam-ple.This ensemble is perhaps the most elegant example and it provides a framework within which the main results can be presented easily.Once the basic concepts are absorbed，their extensions to more general cases is typically routine and several such extensions (but not an exhaustive list) are discussed.

汤姆·理查森（Tom Richardson）是美国国家工程院院士，目前担任高通公司（Qualcomm）的副总裁，他博士毕业于麻省理工学院，后在贝尔实验室任职十年。鲁迪格·厄本克（Rüdiger Urbanke）是瑞士洛桑联邦理工学院的计算机与通信科学学院院长，并曾担任IEEE信息论学会的主席，他博士毕业于圣路易斯华盛顿大学，也曾在贝尔实验室任职多年。两位作者是国际上低密度奇偶校验（LDPC）码研究的领军人物，多次获得过信息论学会的年度论文奖（IEEE Information Theory Society Paper Award），并共同获得过2011年的“小林宏治计算机与通信奖”（IEEE Koji Kobayashi Computers and Communications Award）和2014年的“汉明奖章”（IEEE Richard W. Hamming Medal）。

This book is all about iterative channel decoding.Two other names which are often used to identify the same area are probabilistic coding and codes on graphs.Itera-tive decoding was originally conceived by Gallager in his remarkable Ph.D.thesis of 1960.Gallager's work was，evidently，far ahead of its time.Limitations in com-putational resources in the 1960 were such that the power of his approach could not be fully demonstrated，let alone developed.Consequently，iterative decoding at-tracted only passing interest and slipped into a long dormancy.It was rediscovered by Berrou，Glavieux，and Thitimajshima in 1993 in the form of turbo codes，and then independently in the mid iggos by MacKay and Neal，Sipser and Spielman，as well as Luby，Mitzenmacher，Shokrollahi，Spielman，and Stemann in a form much closer to Gallager's original construction.Iterative techniques have subsequently had a strong impact on coding theory and practice and，more generally，on the whole of commu-nications.The title Modern Coding Theory is clearly a hyperbole.There have been several other important recent developments in coding theory.To mention one prominent example： Sudan's algorithm and the Guruswami-Sudan improvement for list de-coding of Reed-Solomon codes and their extension to soft-decision decoding have sparked new life into this otherwise mature subject.So what is our excuse? Iter-ative methods and their theory are strongly tied to advances in current comput-ing technology and they are therefore inherently modern.They have also brought about a break with the past.Moreover，the techniques are influencing a wide range of applications within and beyond communications，connecting that area with many modern topics in，among others，statistical mechanics and complexity theory.Nev-ertheless，the font on the book cover expresses the irony that the roots of "modern"coding go back to a time when typewriters ruled the world.The field ofiterative decoding has not settled in the same way that classical cod-ing has.There are nearly as many flavors ofiterative decoding systems-and graphi-cal models to represent them-as there are researchers in the field.We have therefore decided to focus more on techniques to analyze and design such systems rather than on specific instances.In order to present the theory，we have elected Gallager's orig-inal ensemble oflow-density parity~check (LDPC) codes as a representative exam-ple.This ensemble is perhaps the most elegant example and it provides a framework within which the main results can be presented easily.Once the basic concepts are absorbed，their extensions to more general cases is typically routine and several such extensions (but not an exhaustive list) are discussed.