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