E-Book Content
Math 422 Coding Theory John C. Bowman Lecture Notes University of Alberta Edmonton, Canada January 27, 2003 c 2002 John C. Bowman ALL RIGHTS RESERVED Reproduction of these lecture notes in any form, in whole or in part, is permitted only for nonprofit, educational use. Contents Preface 5 1 Introduction 1.A Error Detection and Correction . . . . . . . . . . . . . . . . . . . . . 1.B Balanced Block Designs . . . . . . . . . . . . . . . . . . . . . . . . . 1.C The ISBN code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 7 14 17 2 Linear Codes 2.A Encoding and Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 2.B Syndrome Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 21 25 3 Hamming Codes 28 4 Golay Codes 32 5 Cyclic Codes 36 6 BCH Codes 45 7 Cryptographic Codes 7.A Symmetric-Key Cryptography . . . . . . . . . 7.B Public-Key Cryptography . . . . . . . . . . . 7.B.1 RSA Cryptosystem . . . . . . . . . . . 7.B.2 Rabin Public-Key Cryptosystem . . . . 7.B.3 Cryptographic Error-Correcting Codes A Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 53 56 56 59 60 61 3 List of Figures 1.1 Seven-point plane. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 15 Preface These lecture notes are designed for a one-semester course on error-correcting codes and cryptography at the University of Alberta. I would like to thank my colleagues, Professors Hans Brungs, Gerald Cliff, and Ted Lewis, for their written notes and exampl