Date of Award

8-2007

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Mathematical Science

Advisor

Key, Jennifer D

Abstract

Permutation decoding is a technique, developed by Jessie McWilliams in 1960's. It involves finding a set of automorphisms of the code, called a PD-set. If such a set exists and if the generator matrix of the code is in standard form then a simple algorithm using this set can be followed to correct the maximum number of errors of which the code is capable. Primarily this method was used originally on cyclic codes and Golay codes.
In this dissertation we study binary codes formed from an adjacency matrix of some classes of graphs and apply the permutation decoding method to these codes. First we do a literature survey on the permutation decoding method and list the known results.
We find a full error correcting PD-set for the binary codes from rectangular lattice graphs and we use partial permutation decoding for the codes from line graphs of multipartite graphs. Next we derive codes from hypercubic graphs and show that these codes are self-dual and find 3-PD sets for these codes.
First-order Reed-Muller codes are the simplest examples of the class of geometrical codes. We use the translation group as a partial permutation decoding set and find 4-PD sets for these codes.
Finally we study the complexity of the permutation decoding algorithm and re-state earlier results for the lattice graphs and rectangular lattice graphs.

Share

COinS