Signals and Communication Technology Giovanni Cancellieri Polynomial Theory of Error Correcting Codes Signals and Communication Technology More information about this series at http://www.springer.com/series/4748 Giovanni Cancellieri Polynomial Theory of Error Correcting Codes 123 GiovanniCancellieri InformationEngineering Polytechnic University ofMarche Ancona Italy ISSN 1860-4862 ISSN 1860-4870 (electronic) ISBN 978-3-319-01726-6 ISBN 978-3-319-01727-3 (eBook) DOI 10.1007/978-3-319-01727-3 LibraryofCongressControlNumber:2014947130 SpringerChamHeidelbergNewYorkDordrechtLondon ©SpringerInternationalPublishingSwitzerland2015 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthe work. Duplication of this publication or parts thereof is permitted only under the provisions of theCopyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the CopyrightClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) To Daniele, my son and pride Preface Error correcting codes represent a widely applied technique for assuring reliable electronic communications and data recording. Although often some codes are introduced without the need for a polynomial approach, the attempt to provide a descriptionwherepolynomialtheoryishoweverpresentcould beofsomeinterest. The intent of this book is to develop such theory, in a unitary way, trying to find severalconceptualbridgesbetweendifferentclassesofcodes(block,convolutional, concatenated,…). This goal requires the introduction of some rather unusual mathematical tools (like interleaved polynomial multiplication or interleaved polynomial division), able to support it. Also some structural transformations, like modified code lengthening or modified H-extension, are needed in order to con- struct a coherent model, able to support noticeable new interpretations. Theintroductionofquasi-cycliccodesasatruegeneralizationoftheconceptof cyclic codes is only an example of the fruitful use of such mathematical tools and geometrical transformations. They are also important for giving an intuitive justi- ficationfortheencodercircuitstobeadopted.Statediagrams,constructedonthese encoder circuits, contribute to give a better understanding of the properties char- acterizing the codes under study, besides the measure of the decoding computa- tional complexity. The distinction between well-designed and not well-designed convolutional codes represents another innovative concept. The latter family of codes is equiv- alent to catastrophic convolutional codes, but since they are systematic, the cata- strophic behavior is no longer a problem. On the other hand, a more than linear increaseinthenumberoflow-weightcodeframeswiththenumberofframeperiods remainsadrawbackfornotwell-designedconvolutionalcodes,togetherwithsome difficulties in their parity check matrix determination and tail-biting arrangement organization.Directproductcodesbetweenapairofblockcodesaredemonstrated to be a subset of not well-designed convolutional codes. Some further conceptual (and rather surprising) bridges between block codes and convolutional codes are constructed. The treatment is organized maintaining distinct the approaches based on the generator matrix and on the parity check matrix. The reader is gradually guided to vii viii Preface theinterpretationofsuchviewpoints.Someconcepts,derivingfromdualproperties, willappearinalltheirstrongefficacyonlyatthismoment.Modifiedlengtheningof cyclic codes and modified H-extension of cyclic codes are dual opportunities leadingtoanewcomprehensionoftheintrinsicnatureofconvolutionalcodes.The former is obtained by acting on the generator matrix, and the latter on the parity checkmatrix.Thesamecanbemadeforquasi-cycliccodes.Propertransformation of control symbols into information symbols and vice versa supports the above modifications. Modern coding (mainly regarding turbo codes and LDPC codes) is a topic, which is faced after a wide application of the above innovative concepts, so allowing a comprehensive understanding of the structures characterizing such codes. For instance, modified H-extension of quasi-cyclic codes offers the possi- bilityofsettingupasortofdoublyconvolutionalLDPCcode,inturninterpretedin relationtoproperturboproductschemes.TheintroductionofBPGcodes(Binomial Product Generator codes) allows to treat array LDPC codes and some forms of concatenated LDPC codes, together with their convolutional versions, not only by means of the parity check matrix. The continuous search for ultimate extremely good performance, present in the recent literature, has the consequence of reducing attention to the above theoretic aspects. The dominant use of computer simulations and optimization procedures often entails a nonexhaustive investigation of the true geometrical nature of the code under study. Many code families, apparently very different, on more careful analysis, would appear instead strictly related. All these considerations may pro- duce interesting future theoretical developments. To this purpose, the present comprehensive approach would give a possible contribution. About 250 Definitions, 300 propositions (Theorems, Corollaries, Lemmas), nearly 500 examples, highly interconnected, can give an idea of the amount of contentstreated.InfourAppendicessomeusefulconcepts,notstrictlyrelatedtothe topics under development, are collected. They are devoted to nonskilled readers, who need auxiliary assistance for framing such theory in a proper context. Acknowledgments I wish to thank Marco Baldi for fruitful discussions and continuous help in obtainingmostpartofthenumerical computations,FrancoChiaraluceforhishints and theoretical support, Andrea Carassai for some intuitive views, my students at the Polytechnic University of Marche for their contribution in the organization of some material, and finally Laura Fonti for typewriting help and figure assembling. AparticularacknowledgmentisdevotedtoMarcoChianiforhavingreviewedpart of the content, when it was under development. I am also indebted to Rossano Marchesani, Roberto Garello, Torleiv Klove, for our collaboration during the long research activity at the basis of the present work. Contents Part I Generator Matrix 1 Generator Matrix Approach to Linear Block Codes. . . . . . . . . . . 3 1.1 Additive n × n Linear Transformation of a Binary Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Generator Matrix G of a Linear Block Code. . . . . . . . . . . . . 5 1.3 Polynomial Description of the Generator Matrix in a Linear Block Code. . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Properties of a Linear Block Code Derived from the Structural Characteristics of g(x) . . . . . . . . . . . . . . 15 1.5 Systematic Encoder Circuit. . . . . . . . . . . . . . . . . . . . . . . . . 19 1.6 Code Concatenation: Effects on G Matrix . . . . . . . . . . . . . . 21 1.7 Code Puncturation: Effects on G Matrix. . . . . . . . . . . . . . . . 28 1.8 Cyclic Block Codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.9 Enumeration of all the Possible Cyclic Codes of Length N. . . 37 1.10 Shortened Cyclic (SC) Codes. . . . . . . . . . . . . . . . . . . . . . . 44 1.11 Lengthened Cyclic (LC) Codes. . . . . . . . . . . . . . . . . . . . . . 47 1.12 Subcode of an s.s. Time-Invariant Polynomial Code . . . . . . . 56 1.13 Modified Lengthened Cyclic (MLC) Codes . . . . . . . . . . . . . 58 1.14 State Diagrams. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 1.15 Direct Product Codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 1.16 Generator Matrix of a Direct Product Code . . . . . . . . . . . . . 73 1.17 Direct Product Codes as MLC Codes . . . . . . . . . . . . . . . . . 75 1.18 Interpretation of Particular Direct Product Codes by Means of GPC Codes. . . . . . . . . . . . . . . . . . . . . . . . . . 76 1.19 Cyclic and Pseudo-Cyclic Codes in a Non-binary Alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 1.20 Q-ary State Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 1.21 Main Families of Non-binary Block Codes. . . . . . . . . . . . . . 85 ix x Contents 1.22 Reed-Solomon Codes and Other MDS Non-binary Codes . . . 89 1.23 Trellis for an s.s. Time-Invariant Block Code Obtained from Its Generator Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 95 References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 2 Wide-Sense Time-Invariant Block Codes in Their Generator Matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 2.1 Periodically Time-Varying Generator Matrix . . . . . . . . . . . . 101 2.2 Quasi-Cyclic Codes (QC) as a Widening in the Concept of Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 2.3 Quasi-Cyclic Codes with Distributed Control Symbols Described with Their G Matrix. . . . . . . . . . . . . . . . . . . . . . 112 2.4 Representation of Known Block Codes as QC Codes with Distributed Control Symbols. . . . . . . . . . . . . . . . . . . . 117 2.5 Relation Between Some Binary QC-Codes and Cyclic or Pseudo-Cyclic Codes in a Q-Ary Alphabet. . . . . . . . . . . . 119 2.6 Encoder Circuits Based on the G Matrix for a QC Code . . . . 121 2.7 Shortened Quasi-Cyclic (SQC) Codes . . . . . . . . . . . . . . . . . 125 2.8 Lengthened Quasi-Cyclic (LQC) Codes. . . . . . . . . . . . . . . . 130 2.9 Subcode of a w.s. Time-Invariant Polynomial Code. . . . . . . . 136 2.10 Modified Lengthened Quasi-Cyclic (MLQC) Codes. . . . . . . . 138 2.11 Trellis for a w.s. Time-Invariant Block Code Obtained from Its Generator Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 143 References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 3 Generator Matrix Approach to s.s. Time-Invariant Convolutional Codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 3.1 Traditional View of Non-systematic s.s. Time-Invariant Convolutional Codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 3.2 State Diagram and Minimum Distance. . . . . . . . . . . . . . . . . 154 3.3 Systematic Convolutional Codes. . . . . . . . . . . . . . . . . . . . . 162 3.4 Low-Rate Convolutional Codes . . . . . . . . . . . . . . . . . . . . . 166 3.5 High-Rate Punctured Convolutional Codes. . . . . . . . . . . . . . 172 3.6 Recursive Systematic Convolutional (RSC) Codes. . . . . . . . . 176 3.7 Equivalence Between MLC Codes and s.s. Time-Invariant Convolutional Codes . . . . . . . . . . . . . . . . . . 180 3.8 Strict-Sense Time-Invariant High-Rate Convolutional (MLC) Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 3.9 A First Bridge Between Cyclic Block Codes and s.s. Time-Invariant Convolutional Codes . . . . . . . . . . . . . . . . . . 190 3.10 Tail-Biting s.s. Time-Invariant Convolutional Codes . . . . . . . 195 3.11 Trellis of an s.s. Time-Invariant Convolutional Code Obtained from Its Generator Matrix . . . . . . . . . . . . . . 199 References. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203