Foundations of Coding Theory

During the sixteenth century, Cardano wrote a fascinating work called The Book on Games of Chance. In it he gives an extremely candid recount­ ing and personal appraisal of some aspects of his most remarkable life. * One feature of the book is striking for the modern scientist or mathemati­ cian accustomed to current publishing practices. It is brought out during Cardano's discussion of his investigations of certain special questions of applied probability, namely, the question of how to win at gambling. His technique is simplicity itself: in fine reportorial style he reveals his proposed strategy for a particular gambling game, giving marvelous motivating arguments which induce the reader to feel warm, heartfelt support for the projected strategy. Then with all the drama that only a ringside seat observation can bring, Cardano announces that he tried the strategy at the casino and ended up borrowing his taxi fare. Undaunted by failure, he analyzes his now fire-tested strategy in detail, mounts new and per­ suasive arguments, and, ablaze with fresh optimism and replenished resources, charges off to the fray determined to now succeed where he had so often failed before. Along the way, Cardano developed a number of valuable insights about games of chance and produced useful research results which presumably would be of interest in our present-day society. However, he could never publish the results today in journals with all the flair, the mistakes, the failures and minor successes which he exhibits in his book.

Contenu

I / Introduction.- 1. Basic Problems of Abstract Coding Theory.- 1. The Setting for the Study.- 2. Models.- 3. The Setting for the Definitions.- 4. Definitions.- 5. A Guide to the Book.- 2. Basic Properties of Error-Correcting Codes.- 1. Introduction.- 2. Description of the Error Patterns.- 3. Correcting Ability and Decodability.- 4. Synchronizability and Comma-Freedom.- II / Theoretical Studies.- Overview.- 3. A Study of Error-Correcting Codes, I.- 1. Introduction.- 2. Preliminaries.- 3. Mappings Associated with a Code.- 4. Irredundant and Precorrecting Codes.- 5. Correcting Codes.- 4. A Study of Error-Correcting Codes, II: Decodability Properties.- 1. Introduction.- 2. Codes and Mappings.- 3. Correcting Codes.- 4. Decodable Codes.- 5. Prompt Codes.- 5. A Study of Error-Correcting Codes, III: Synchronizability and Comma-Freedom.- 1. Introduction.- 2. Synchronizable Codes.- 3. Comma-Free Codes.- 4. Diagrams and Tables.- 6. A Study of Error-Correcting Codes, IV: Code Properties and Unambiguous Sets.- 1. Introduction.- 2. Extension of Concepts.- 3. Scansions.- 4. Code-Related Properties.- 7. Some General Results of Abstract Coding Theory with Applications to the Study of Codes for the Correction of Synchronization Errors.- 1. Introduction.- 2. Separation for a Binary Relation.- 3. Error-Correcting Capability.- 4. Error-Decoding Capability.- 5. Error-Limiting Capability.- 6. On the Levenshtein Distance.- 7. Error-Correcting for the Levenshtein Metric.- 8. A Sufficient Condition for Decodability.- III / Tests and Constructions.- Overview.- 8. The Sardinas/Patterson and Levenshtein Theorems.- 1. Introduction.- 2. The Residual Quotient.- 3. Characterization of ?n(C, D).- 4. Unique Decipherability.- 5. A Finiteness Condition. Codes with Bounded Delay.- 6. Synchronizable Codes.- 7. Some Numerical Bounds.- 9. Generalization of Tests for Certain Properties of Variable-Length Codes.- 1. Introduction.- 2. Definitions and Examples.- 3. A Construction Involving Gauged Sets.- 4. Tests for Certain Properties of Codes.- 5. Application of the Tests to Example Codes.- 10. On a Family of Error Correcting and Synchronizable Codes.- 1. Introduction.- 2. Definitions.- 3. Code Properties.- 4. Properties of N-Sets.- 5. Examples.- 11. A Family of Codes for the Correction of Substitution and Synchronization Errors.- 1. Introduction.- 2. The Codes Anc.- 3. Some General Results.- 4. The Codes Anc have Properties (1) and (2).- Epilogue.- Selected Bibliography on Coding Theory (1957-1968) from Parke Mathematical Laboratories.- References.- Index of Authors.- Index of Subjects.