University of California

at

Santa Barbara

Error-Correcting Codes:

A Practical Look at Block Codes

A thesis submitted in partial satisfaction of the

requirements for the degree of

Master of Arts

in

Mathematics

by

Vahe Petrossian

Committee in charge:

Professor Morris Newman, Emeritus, Chairman

Professor Xu-Dong Liu

Professor John C. Bruch, Jr.

July 1997

The thesis of

Vahe Petrossian

is approved:

Committee Chairman

July 1997

VITA

March 7, 1973---Born---Tehran, Iran

1988---California State University, Los Angeles

1992-95---Logistical Support, United States Army

1995---B.A., Occidental College

1995-97---Mobilization Support, United States Navy

1996-97---Teaching Assistant, Department of Mathematics,

University of California, Santa Barbara

PUBLICATIONS

Error Correcting Codes: Construction of the Hamming and Golay Codes. Unpublished B.A. thesis, Occidental College, 1991. 24 pp

FIELDS OF STUDY

Major Field: Error Correcting Codes

Studies in Computer Science: Vector Programming in 3-D Frame Modeling

Studies in Field Theory: Unsolvability of the Quintic using Galois Fields

Studies in Error Correcting Codes: Constructions of Hamming and Golay Codes

Abstract

Error-Correcting Codes:

A Practical Look at Block Codes

by

Vahe Petrossian

The birth of digital technology in the 1940s sparked the birth of a new branch in Mathematics: Error Correcting Codes. Since the rise of digital technology Error Correcting Codes have played an integral part in society. Reliable transmission of vital data is a crucial topic. Therefore some kind of protection against error during transmission is called for. Let us denote by GF[2] the Galois Field with two elements. We take the set GF[2ⁿ] of all ordered n-tuples over GF[2] denoted by V(n), and define two operations within V(n): addition and multiplication. This vector space of n dimensions has scalar values zero and one where the elements are called words. Any subset C of this vector space forms a code. If C has the property that the sum of any two codeword is a codeword then the code C is called a linear code. Thus any k-dimensional subspace of a vector space of dimension n forms an (n,k)-code. These codes can also be constructed using polynomials. Let F[x] denote the ring of polynomials in x over the field F. In what follows F will be taken as GF[2] , the finite field with 2 elements. The factors of ( xⁿ - 1) are examined, and a monic irreducible polynomial, g(x), of least degree is chosen as the generator polynomial of a code C. Using this as a means for generating codes we can construct various scenarios to simulate data transmission. The data from these simulations give us an idea of the efficiency of the codes and potential modifications for improving efficiency. In one case the meshing of block codes actually improved data transmission reliability when burst errors occur.

Table of Contents

Chapter 1. Introduction to Error-Correcting Codes

1. Motivation 1

2. Introduction by example 2

3. Main Coding Process 3

4. Brief Historical Introduction 5

Chapter 2. Linear Block Codes

1. Redundancy is Good 7

2. A Typical Coding Scheme 8

3. Binary Linear Codes 10

4. Encoding with Linear Codes 12

5. Standard Form 13

6. Decoding with Linear Codes 14

7. Syndrome Decoding 16

Chapter 3. Polynomial Codes

1. Constructing Linear Codes 20

2. (7,4)-code Example 22

3. (23,12)-code Example 23

4. The Factor List 25

5. Generator Matrix 27

6. Check Matrix 28

Chapter 4. Sending and Receiving Codes: Simulations

1. Programming Aspect: Transmission Simulation 30

2. Random Error Data Transmission Simulations 30

3. Results 36

Chapter 5. Modified Encoding and Decoding Technique

1. Burst Errors vs. Non-Burst Errors 42

2. Meshing 44

3. Programming Aspect: Burst Errors 45

4. Burst Error Control Simulations 46

5. Results 47

Bibliography 53

Appendices 55

Acknowledgments

I take this opportunity to express my sincere gratitude to Dr. Donald Goldberg and Dr. Morris Newman. During my undergraduate studies, Dr. Goldberg introduced me to the fascinating world of Error-Correcting Codes. Weekly discussions with Dr. Goldberg were truly motivating. Dr. Goldberg rendered my new found interest in Error-Correcting Codes. Following my Bachelors Thesis, Dr. Newman gave me initiative to write a Masters Thesis on Error-Correcting Codes.

I would like to extend my gratitude to my family who supported me to this point in my life. I thank my uncles Mr. Nejdeh Pirjani and Mr. Vrej Pirjanian. Nejdeh inspired me in the sixth grade to study mathematics and Vrej became a father figure to me once my father past away. I thank my mother Carmen Petrossian who on her own for 20 years raised my sister and I. My mom has always pushed me to my potential. And I thank my fiancee, Karmen Atayan, for her support and patience for the past 5 years.

Acknowledgments

I take this opportunity to express my sincere gratitude to Dr. Donald Goldberg and Dr. Morris Newman. During my undergraduate studies, Dr. Goldberg introduced me to the fascinating world of Error-Correcting Codes. Weekly discussions with Dr. Goldberg were truly motivating. Dr. Goldberg rendered my new found interest in Error-Correcting Codes. Following my Bachelors Thesis, Dr. Newman gave me initiative to write a Masters Thesis on Error-Correcting Codes.

I would like to extend my gratitude to my family who supported me to this point in my life. I thank my uncles Mr. Nejdeh Pirjanian and Mr. Vrej Pirjanian. Nejdeh inspired me in the sixth grade to study mathematics and Vrej became a father figure to me once my father past away. I thank my mother Carmen Petrossian who on her own for 18 years raised my sister and I. My mom has always pushed me to my potential. And I thank my fiancee, Karmen Atayan, for her support and patience for the past 5 years

To my

Mother

Chapter 1 Introduction to Error-Correcting Codes

1. Motivation

In today's technological society digital communication is present in every aspect of our lives. Satellite data transmissions, network transmissions, computer file transfers, radio communications, and cellular communications transfer data information through a channel that is prone to error. In each case information transmitted from the sender to the receiver has the possibility to accrue error; at the same time the receiver has no clue to whether or not the message received contains any errors or not. Since the receiver has no a priori knowledge of the information being sent, some type of encoding⁽¹⁾ or redundancy⁽²⁾ of the information is needed to increase the probability of a successful transmission.

2. Introduction by Example

In 1965 Mariner 4 was the first satellite to take pictures of Mars[6]. Each picture was a 200x200 pixel image with a total of 240,000 bits of information, since there are six bits per pixel. This meant 240,000 bits of information needed to be transmitted approximately 78 million miles! Technology in 1965 allowed data to be transmitted at a rate of only 8 1/3 bits per second. Thus, it took eight hours to send each picture. If any repetition was to be incorporated, each picture would have taken an implausible amount of time.

3. Main Coding Process

It is necessary to become familiar with several keywords and basic concepts to understand error-correcting codes. These include: coding, the Main Coding Idea, block codes, and instantaneous codes.

Coding is defined by two finite sets, A and B, where the coding scheme is an onto function from A onto B. The sets A and B are commonly referred to as the source alphabet and the code alphabet respectively.

There are two main types of coding schemes: block codes and instantaneous codes. Block codes are codings that have codewords of a fixed length, n. For example, the hexadecimal code and ASCII code are both block codes. Instantaneous codes are codings where no codeword is a prefix of any other codeword. For example, Morse code is an instantaneous code since a space is only used at the end of each codeword. We shall examine block codes.

The time problem we encountered with repetition codes gives us motivation to look for better coding methods. In 1947, Hamming noted that the two main requirements of devising a new coding method are to have an error detecting scheme and an error correcting scheme. In the repetition code we have error detection and correction capabilities but only at the expense of efficiency.

4. Brief Historical Introduction

The idea of Error Correcting Codes came with the onslaught of computer technology. In the late 1930s Bell Telephone Laboratories built one of the first mechanical relay computers. This computer is unlike anything currently in use. However, the mechanical relay computer while executing a program was prone to errors like nowadays computers. In fact, in 1947 Hamming⁽⁶⁾ conducted calculations on the mechanical relay computer at Bell Telephone Laboratories and found himself constantly re-running his programs due to computer halts. In an interview Hamming commented:

"Two weekends in a row I came in and found that all my stuff had been dumped and nothing was done...And so I said, "Damn it, if the machine can detect an error, why can't it locate the position of the error and correct it?"[12]

The relay computers operated with self-checking codes only, called two-out-of-six-holes. The machine would detect the error then halt the current job and move to the next. The coding technique used is similar to a repetition code.

"...the input was entered in the machine via a punched paper tape, seven-eights of an inch wide, which had up to six holes per row. Each row was read as a unit. If the sensing relays expected a two-out-of-six code, they would prevent further computation if more or less than two holes appeared in a given row..."[12]

With the two-out-of-six-holes coding technique the relay computer halted two or three times a day. The need for a better code was apparent once the computer became 10³ times faster--i.e. the computer would stop two or three hundred times a day. Hamming knew that if a repetition code was to be used the Relay Computer would grow in size as the computer became faster. Therefore a single error-correcting code with minimum redundancy was needed. This code was to be called the (7,4) Hamming Code.

Chapter 2. Linear Block Codes

1. Redundancy is Good

The key to error detection and correction lies in redundancy of information. There is no other way around it. We must add more bits of information to our source code (message) to gain a higher probability of an accurate transmission. This is due to the nature of the transmission. For example, let us say the sender transmits the message, "Do not fire missiles" and the receiver receives, "Do fire the missiles". At this point the receiver will follow the orders and fire the missiles without a second thought since the receiver has no clue if the message is in error and if it is in error what the correct message is. Now if the receiver receives, "Do fire the missiles...Do not fire the missiles...Do not fire the missiles." The receiver will not fire the missiles assuming that there is a greater probability that the correct message is, "Do not fire the missiles" since it was receive twice rather than once. This same concept of redundancy is also incorporated in modern day codes but with much greater efficiency than just repeating the source code (message.)

2. A Typical Coding Scheme

Let us say we have two binary words of length two in our source code (message) that we wish to create a coding scheme for: source code: (00, 11). Consider the following binary words:

A more visual approach to this coding scheme is by taking each binary word and plotting it on a Cartesian coordinate system where the first, second, and third position of a binary word is x, y, z respectively. The following graph is produced:

Notice that for each codeword there is a corresponding word that is exactly distance 1 away from a word.

3. Binary Linear Codes

Linear block codes are codes that have codewords of a fixed length n and the sum of any two codeword is another codeword. So how do we form such codes? Let us denote GF(2) as the Galois Field with two elements. We take the set GF(2ⁿ) of all ordered n-tuples over GF(2) denoted by V(n), and define two operations within V(n):

(i) addition: if x = (x₁ , x₂ , . . . , x_n ) and y = (y₁ , y₂ , . . . , y_n ) V(n), then

x + y = (x₁ +y₁ , x₂ + y₂, . . . , x_n + y_n)

(ii) multiplication: if x = (x₁ , x₂ , . . . , x_n ) V(n) and a GF(2), then

ax = (ax₁ , ax₂ , . . . , ax_n )

V(n) is a vector space of dimension n since for all u, v, w V(n) and for all a, b, GF(2) we have

(i) u + v V(n)

(ii) (u + v) + w = u + (v + w)

(iii) the all-zero vector 0 = (0, 0, . . ., 0) V(n) and satisfies u + 0 = 0 + u = u

(iv) Given u = (u₁ , u₂ , . . . , u_n ) V(n), the element -u = (-u₁ , -u₂ , . . . , -u_n ) V(n) and satisfies u + (-u) = 0

(v) u + v = v + u

(vi) (Closure under scalar multiplication av V(n)

(vii) (Distributive laws) a(u + v) = au + av, (a + b)u = au + bu

(viii) (ab)u = a(bu)

(ix) 1u = u, where 1 is the multiplicative identity of GF(2)

This n-dimensional vector space has scalar values zero and one. Any subset C of this vector space forms a code. But, the code is special. It has the unique property that the sum of any two codewords is another codeword. Thus we get a binary linear code C if and only if it satisfies the property that the sum of any two codewords is a codeword which is exactly a k-dimensional subspace of the n-dimensional vector space. Note that not every code C is linear, and that we have many more non-linear codes than linear ones. There is nothing wrong with non-linear codes, in fact at times non-linear codes are much more efficient, however, we will soon see why we sacrifice efficiency to use linear codes. We have a linear vector subspace with a basis. To describe the subspace we need only k codewords, since linear combinations of these k codewords span the k-dimensional subspace. This is the motivation for working with linear codes instead of non-linear codes. With a linear code we need only list k codewords to determine the rest of the codewords whereas with a non-linear code we need to list all the codewords, that is 2^k codewords. This hints at the possibility of a generator matrix⁽⁸⁾ --i.e. a matrix that can generate (list) all the elements of the subspace⁽⁹⁾. The subset C, a k-dimensional subspace of an n-dimensional vector space, is called a binary linear code or an (n,k)-code⁽¹⁰⁾.

4. Encoding with Linear Codes

Encoding with a linear (n,k)-code is quite easy. Given a message vector u = (u₁, u₂, . . ., u_k) multiply on the right by the generator matrix G. The result is the codeword. Take for example the (7,4)-code with the following 4x7 generator matrix.

The following summarizes the encoding process:[6]

5. Standard Form

Two generator matrices of an (n,k)-code are called equivalent if one can be obtained from the other by a combination of operations. The following is the list of operations allowed:

(R1) Permutation of the rows

(R2) Multiplication of a row by a non-zero scalar

(R3) Addition of a scalar multiple of one row to another

It should be clear that the above operations preserve linear independence and thus will not change the structure of the matrix.

Let G be a generator matrix of an (n,k)-code and define the standard form as G = [ I_k | A ], where I_k is the kxk identity matrix, and A is a k x (n - k) matrix.

By performing operations of the above types, G can be transformed into standard form.⁽¹¹⁾

6. Decoding with Linear Codes

Once the source code or message has been encoded and transmitted the receiver needs a process that will decode the codeword they received and retrieve the message. The decoding has two main steps: error detection and error correction. Error detection is quite simple: if the codeword received is not one of the codewords in the receiver's list then there must be an error. Error correction is a bit more involved but it is easily implemented.

First we will define the dual code of C , where C is a linear (n,k)-code, denoted by C . The dual code of C is the set of vectors of V(n) which are orthogonal to every codeword of C:

C = {v V(n) | v u = 0 for all uC }

Now we define the parity check matrix. A parity check matrix H for an (n,k)-code C is a generator matrix of C. So GH^T = 0, where G is the generator matrix of an (n,k)-code and H^T is the transpose of the parity check matrix. Consequently we have,

C = { x V(n) | x H^T = 0 } .⁽¹²⁾

Due to this property we have the ability to now take the codeword we received and multiply it to the parity check matrix H and check the codeword for any errors. If any errors have occurred during transmission then x H^T 0 . So how do we form the parity check matrix? We can do this by using the generator matrix. If G = [ I_k | A ] is the standard form generator matrix of an (n,k)-code C, then a parity check matrix for C is H = [ A^T | I_n-k ] .

Proof:⁽¹³⁾ Suppose

Then H has the size required of a parity check matrix and its rows are linearly independent. Hence it is enough to show that every row of H is orthogonal to every row of G. But the inner product of the ith row of G with the jth row of H is

0 + . . . + 0 + (a_ij) + 0 + . . . + 0 + a_ij + 0 + . . . + 0 = 0 .[6]

7. Syndrome Decoding

So far we have discussed in detail on how to encode a message. We now need a method of decoding the codewords received. The most efficient system of decoding is called syndrome decoding. The syndrome of a codeword is simply defined by the multiplication of the codeword received by the check matrix H:

S(c) = c^T H , where c C and H is the check matrix

We first define cosets and coset leaders. Suppose that C is an (n,k)-code and that a is any vector in V(n). Then the set a + C defined by

a + C = { a + x | x C }

is called a coset of C. For example consider the (4,2)-code C = {0000, 1011, 0101, 1110}. The cosets of C are:

0000 + C = {0000, 1011, 0101, 1110}

1000 + C = {1000, 0011, 1101, 0110}

0100 + C = {0100, 1111, 0001, 1010}

0010 + C = {0010, 1001, 0111, 1100}

And the coset leader is the codeword that when summing the digits of the codeword results in the smallest integer. For example, the smallest integer in summing the digits of the following codewords is 1:

1000 => 1+0+0+0 = 1

0011 => 0+0+1+1 = 2

1101 => 1+1+0+1 = 3

0110 => 0+1+1+0 = 2

The one-to-one correspondence of error correction is achieved by creating a syndrome look-up table. A syndrome look-up table is a table of binary words that associates each syndrome to a coset leader. The syndrome look-up table is defined by:

S(z) = z^TH , where z is a coset leader and H is the check matrix.

For example,

Chapter 3. Polynomial Codes

1. Constructing Linear Codes

A clear distinction between polynomial codes and binary codes is that the elements of polynomial codes are polynomials with coefficients in GF[2] and the elements of binary codes are binary sequences. For example, the following two codes are equivalent yet are represented differently:

Binary Code: {000, 101, 011, 110}

Polynomial Code: {0, x² + 1, x + 1, x² + x}

Basically it boils down to a matter of notation; except for the fact that a rich algebraic structure exists and can be readily seen through the notation of polynomials.

A code C is cyclic if C is a linear code and any cyclic shift of a codeword is also a codeword.⁽¹⁴⁾ For example consider the following binary code {000, 101, 011, 110}. Other than 000 codeword, the other codewords can be cycled to the left or right and they end up with a codeword in the binary code. Having this cyclic property is a great asset. A lot of algebraic structure exists in cyclic codes. In fact cyclic codes are choice candidates when it comes to chip programming since they can easily be implemented by shift registers.⁽¹⁵⁾

Consider GF[2] denoted by F. Take the ring of polynomials F[x] and mod out by x ⁿ-1 => F[x]/(x ⁿ-1). We shall denote the ring F[x]/(x ⁿ-1) by R_n. A code C in R_n is a cyclic code iff C satisfies the following conditions:

1) a(x), b(x) C => a(x)+b(x) C

2) a(x) C and r(x) is in R_n => r(x)a(x) C

Hence cyclic codes are ideals of the ring R_n. Now let f(x) be any polynomial in R_n and denote by <f(x)> the subset of R_n consisting of all multiples of f(x) reduced mod (x ⁿ-1). Basically <f(x)> = {r(x)f(x) | r(x) is in R_n}

We say the code is generated by f(x) when for any f(x) in R_n, the set <f(x)> is a cyclic code. For example, consider the code C = <1+x ²> in R₃. Multiplying 1+x ² by each of the eight elements of R₃ and reducing mod x ³-1 produces only four distinct codewords: 0, 1+x, 1+x², x+x². Thus C is the code {000,110,101,011}. Therefore if C is a cyclic code in R_n, then

1) there exists a unique irreducible monic polynomial g(x) in C

2) C = <g(x)>

3) g(x) is a factor of x ⁿ-1

g(x) is called the generating polynomial.⁽¹⁶⁾ For example, x ³-1 = (x+1)(x ²+x+1). We have (x+1) and (x ²+x+1) irreducible over GF[2]. If we pick g(x) = (x+1) we get {0,1+x,1+x ²,x+x ²} We can also pick g(x) = (x ²+x+1) and get {0,1+x+x ²}. Remember we are working modulo (x ³-1)

2. (7,4)-code Example

Using f(x) = x⁷ - 1, we have x⁷ - 1 =(x - 1)(x³ + x + 1)(x³ + x² + 1) over GF(2). From our work above the polynomial g(x) = x³ + x² + 1 generates the cyclic (7,4)-code, called the generator polynomial: {x³ g(x) = 1101000,x² g(x) = 0110100, x g(x) = 0011010, g(x) = 0001101}. In addition, the check matrix is constructed by H = [ A^T | I_n-k ] using the generator matrix in standard form: G = [ I_k | A ].

3. (23,12)-code Example

Using f(x) = x²³ - 1, we have the factors x²³ - 1 = (x-1)(x¹¹ + x¹⁰ + x⁶ + x⁵ + x⁴ + x² + 1)(x¹¹ + x⁹ + x⁷ + x⁶ + x⁵ + x + 1). Our generator polynomial becomes g(x) = (x¹¹ + x¹⁰ + x⁶ + x⁵ + x⁴ + x² + 1) with the following generator matrix:

4. The Factor List

The next page is a list of (xⁿ - 1) factors over GF[2]. Using the Mathematica command "Do[Factor[x^Prime[n] - 1, Modulus->2],{n,1,15}]" the factors of (xⁿ - 1) over GF[2] are easily achieved. Notice that in each factor the degree of the polynomial factors are the same.⁽¹⁷⁾ For example, the factors of (x³¹ - 1) are (1 + x² + x⁵) ( 1 + x³ + x⁵) (1 + x + x² + x³ + x⁵) (1 + x + x² + x⁴ + x⁵) (1 + x + x³ + x⁴ + x⁵) (1 + x² + x³ + x⁴ + x⁵) where each of the factors are of degree 5.

n Factors over GF[2]

5. Generator Matrix

Previously we had a generator matrix and check matrix for encoding and decoding the source code. It would be very convenient if similar matrices for polynomial codes could be constructed. Due to the structure of the cyclic polynomial codes a generator matrix and a check matrix can be formed from the generator polynomial and check polynomial respectively. Given a cyclic code C with a generator polynomial g(x) = g₀ + g₁x + g₂x + ... + g_rx^r of degree r the generator matrix for C is

For example consider the generator polynomial g(x) = x + 1 that generates the code {0,x² + 1, x + 1 ,x² + x } corresponding to {000,101,011,110}. From above, our generator matrix will look like:

6. Check Matrix

Given a cyclic code C with a generator polynomial g(x) = g₀ + g₁x + g₂x + ... + g_rx^r of degree construct the generator matrix converted into standard form: G = [ I_k | A ]. The check matrix is defined by H = [ A^T | I_n-k ].

Chapter 4. Sending and Receiving Codes: Simulations

1. Programming Aspect: Transmission Simulation

The programming language used is called Mathematica 3.0 by Wolfram Research®. The choice of choosing Mathematica 3.0 is obvious due to its powerful programming functions.

The following are programs that first produces a generator and check matrix using the above polynomial code techniques. Second, the program simulates a transmission by prompting the user for the message needed to be sent. The message is then converted to ASCII and then to binary. The binary stream is broken into fixed blocks as to be prepared for encoding. Once the binary blocks have been encoded the program randomly flips bits in the binary stream to simulate noise in a channel. The program then decodes the binary stream using the syndrome technique and displays the resulting message.

2. Random Error Data Transmission Simulations

The following is a sample programming code using the (7,4)-code. The programming codes for the (23,12)-code and (47,23)-code are in the appendix.

Clear[temp,i,k,infoc,infonum,encrypt,char,char1,char2];

(*GENERATOR MATRIX USING POLYNOMIAL CODES*)

(* "N" IS THE DIMENSION OF THE SPACE. "SIZE" IS THE SUBSPACE *)

Clear[b,size,binarycode,i,n,x,MatrixH];

n=7;

binarycode=CoefficientList[(1+x+x^3),x];

size=Count[binarycode,0]+Count[binarycode,1];

(*While[(size<n),binarycode=Append[binarycode,0];size=size+1];*)

Table[b[i]=Part[binarycode,i],{i,1,size}];

Do[

Do[

MatrixG[i,j]=0,{i,1,(n)-(size-1)}],{j,1,(n)}];

Do[

Do[

MatrixG[i,j+i-1]=b[j]

,{j,1,size}],{i,(n)-(size-1)}];

G=Array[MatrixG,{(n)-(size-1),(n)}];

inc=1;

Do[Do[

If [(MatrixG[i-inc,j]==1),G=ReplacePart[G,Mod[Part[G,j]+Part[G,i-inc],2],i-

inc]]

,{i,(n)-(size-1),1,-1}];inc=inc+1,{j,(n)-(size-1),1,-1}];

(*Print[" Generator Matrix " ];

Print[MatrixForm[G]];*)

Do[Do[MatrixH[j-size,i]=Part[G,i,j],{i,1,(n)-(size-1)}],{j,size,n}];

H1=Array[MatrixH,{n-size,size}];

H2=IdentityMatrix[n-size];

H=Transpose[Join[Transpose[H1],H2]];

Print[" Check Matrix " ];

Print[MatrixForm[H]];

(*Creating Syndrome Look-up Table*)

(* GENERATES ALL POSSIBLE INFO POSITIONS..READY TO BE ENCODED

FOR ALL POSSIBLE CODEWORDS. *)

(* size=4; REMEMBER TO CHECK IF THIS IS CONSISTENT FROM ABOVE*)

temp={0};

pre={0};

Do[temp=Append[temp,0],{ii,1,size-1}];

temp={temp};

Do[pre=Append[pre,0],{ii,1,size-1}];

Do[pre=ReplacePart[pre,1,-k];

preinfo=Permutations[pre];

temp=Join[temp,preinfo],{k,1,size}];

preinfo=temp;

(* GENERATING ALL POSSIBLE CODEWORDS *)

v=1;

Do[

info=Part[preinfo,v];

codes[v]=Mod[Dot[info,G],2];

v=v+1

,{vv,1,2^size}];

(*Designed for (7,4) code. *)

cosetlist={{0,0,0,0,0,0,0},{1,0,0,0,0,0,0},{0,1,0,0,0,0,0},{0,0,1,0,0,0,0},

{0,0,0,1,0,0,0},{0,0,0,0,1,0,0},{0,0,0,0,0,1,0},{0,0,0,0,0,0,1}};

v=1;

Do[

cosetleader=Part[cosetlist,v];

syndrome[v]=Mod[Dot[H,cosetleader],2];

v=v+1

,{vv,1,(2^n) / (2^size)}];

(*Do[Print[" ",syndrome[i]," ", Part[cosetlist,i]],{i,1,8}]*)

syndromelist=Table[syndrome[i],{i,1,(2^n) / (2^size)}];

Do[Do[

(*messagetoencode=InputString["Message to Encode"];

errorsinstream=Input["Please enter number errors"];*)

messagetoencode="This is a fun test!";

(*errorsinstream=7;*)

(* Converting message into a binary code using ascii codes *)

char=ToCharacterCode[messagetoencode];

char1=BaseForm[char,2];

binbasecount=Length[char];

temp={0};

Do[

infoc=ToString[BaseForm[Part[char1,1,i],2]];

infonum=StringLength[infoc];

key=Table[StringTake[infoc,{k}],{k,1,(infonum/2)-1}];

key=ToExpression[key];

While[(Length[key]<8),key=Prepend[key,0]];

temp=Join[temp,{key}]

,{i,1,binbasecount}];encrypt=Delete[temp,1];

(*Print[encrypt];*)

(*Problem part...we need to flatten encrypt and then add bits to the

beginning*)

(*until it is divisable by 4 since we need blocks of 4 to encode*)

If[(Mod[Length[encrypt],size]!=0),

encrypt=Flatten[encrypt];

fix=0;

While[(Mod[Length[encrypt],size]!=0),encrypt=Prepend[encrypt,0];fix=1+fix]

];

encrypt2=Partition[Flatten[encrypt],size];

(*Encoding Encrypt*)

temp={0};

Do[

code=Mod[Dot[Part[encrypt2,i],G],2];

temp=Join[temp,{code}],{i,1,Length[encrypt2]}];

encrypt2=Delete[temp,1];(*Print[encrypt2];*)

(*Sending Stream of Data*)

encodeddatastream=Flatten[encrypt2];

(*Print[encodeddatastream];*)

(*Randomly adding 9 errors to stream*)

Do[

Randomerror=Random[Integer,{1,Length[encodeddatastream]}];

If[(Part[encodeddatastream,Randomerror]==1),errelement=0,errelement=1];

encodeddatastream=ReplacePart[encodeddatastream,errelement,Randomerror]

(*Print["Error added to position : ",Randomerror]*)

,{iii,1,errorsinstream}];

(*Print[encodeddatastream]*)

(*Decoding data stream*)

(*Paritioning data stream back in block code*)

temp={0};

words=Partition[encodeddatastream,n];

Do[

word=Part[words,i];

codesyndrome=Mod[Dot[word,Transpose[H]],2];

pos=Part[Flatten[Position[syndromelist,codesyndrome]],1];

correct=Mod[Part[cosetlist,pos]+word,2];

temp=Join[temp,correct]

,{i,1,Length[words]}];

correct=Delete[temp,1];

correct=Partition[correct,n];

(*Retrieving DATA *)

(*First we delete the parity checks *)

temp={99};

Do[

codewordcorrected=Part[correct,i];

Do[codewordcorrected=Delete[codewordcorrected,-1],{kk,1,n-size}];

temp=Join[temp,codewordcorrected]

,{i,1,Length[correct]}];

infoback=Delete[temp,1];

(*codedinfoback=Partition[infoback,8];*)

(*correct=Partition[infoback,8];*)

correct=Flatten[infoback];

If[(fix!=0),

Do[correct=Delete[correct,1],{kk,1,fix}]];

codedinfoback=Partition[correct,8];

(*Print[codedinfoback];*)

(*Now to convert to Binary*)

i=0;

ascii={0};

Do[

i=i+1;

asciicode=0;

convertedinfo=Delete[Part[codedinfoback,i],1];

pos1=Part[convertedinfo,7];

pos2=Part[convertedinfo,6];

pos3=Part[convertedinfo,5];

pos4=Part[convertedinfo,4];

pos5=Part[convertedinfo,3];

pos6=Part[convertedinfo,2];

pos7=Part[convertedinfo,1];

If[(pos1==1),asciicode=asciicode+1];

If[(pos2==1),asciicode=asciicode+2];

If[(pos3==1),asciicode=asciicode+4];

If[(pos4==1),asciicode=asciicode+8];

If[(pos5==1),asciicode=asciicode+16];

If[(pos6==1),asciicode=asciicode+32];

If[(pos7==1),asciicode=asciicode+64];

ascii=Join[ascii,{asciicode}],

{ii,1,binbasecount}];ascii=Delete[ascii,1];

(*Print[FromCharacterCode[ascii]];*)

(*Counts number of errors even after error-correction*)

(*Errors not detected*)

errorscount=0;

Do[

If[(Part[char,i]!=Part[ascii,i]),errorscount=1+errorscount],{i,1,

binbasecount}];

(*Print["Number of errors = ",errorscount];*)

rawdata[loops]=errorscount

,{loops,1,20}];

(* ^should be the same as ^ upsidedown carat *)

dataplot=Table[{i,rawdata[i]},{i,20}];

g2=Plot[binbasecount,{x,1,20},DisplayFunction->Identity];

g1=ListPlot[dataplot,PlotJoined->True,PlotRange->{0,binbasecount+2},

DisplayFunction->Identity];

Print["Number of Errors incorporated in bit stream = ",errorsinstream];

Show[g1,g2,DisplayFunction->$DisplayFunction,Frame->True,FrameLabel->{

Retransmissions,Errors}]

,{errorsinstream,1,80}]

3. Results

The simulations of the (7,4)-code and the (23,12)-code consisted of transmitting the message "This is a fun test!" 20 times for every error added. 1 to 80 errors were added in each simulation of the (7,4)-code and the (23,12)-code. The results are interesting in that the error correction capabilities of these simple codes are quite good. The following is a list of received transmissions for each error added. Notice how the message deteriorates as the errors are added to the data stream.

(7,4)-code

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fn test!"

"This is a fun test!"

"This is a fun test!"

"This is 1 fun test!"

"This is a fun test!"

"Thip is a fun pest!"

"This iw a fun test!"

"Thip is`a fun test!"

"TXis \ts a fun test!"

"This is 1 fun test!"

"This i9 a veN test!"

"This iu a fsn test!"

"Txis-is#1 Vun test!"

"Thj# is a fuc test!"

"This is a f%n0test!"

(23,12)-code

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"¶his is a fun test!"

"This is a fun test!"

Clearly the (23,12)-code is much better in error-correction. In the following graphs we have taken each retransmission and plotted it versus the number of errors encountered after error-correction. The horizontal line in the top portion of each graph represents the maxium number of errors that can occur. The graphs start from having 1 error to 8 errors in the bit stream and then 73 errors to 80 errors in the bit stream. The graphs are viewed left to right.

(7,4)-code

1 error to 8 errors

73 errors to 80 errors

(23,12)-code

3 errors to 10 errors

73 errors to 80 errors

Chapter 5. Modified Encoding and Decoding Technique

1. Burst Errors vs. Non-Burst Errors

A common⁽¹⁸⁾ malady in data transmission is when a bunch of errors occur sequentially⁽¹⁹⁾. An example of this impulse of noise or burst of errors vs. non-burst of errors is depicted in the following diagram.

Unfortunately, block codes are not immune to burst errors. In fact block codes function very poorly in data transmissions where burst errors occur. The reason being is that a burst of errors can cause a block or codeword to fail the decoding process due to too many errors for the coding scheme to correct. For example, the (7,4)-code and (23,12)-code can only correct 1 and 3 errors per block or codeword respectively⁽²¹⁾. The following diagram illustrates (7,4)-block codes with burst errors and non-burst errors⁽²²⁾.

2. Meshing

Do we have burst error control in block codes? The answer is obviously no. But what if we were to modify the encoding process?

Block codes and burst errors do not mix nicely. So what we need to do is to get rid of the blocks. One approach is meshing the block codes. Consider three block codes a, b, and c:

a₁ a₂ a₃ . . . a_n-2 a_n-1 a_n b₁ b₂ b₃ . . . b_n-2 b_n-1 b_n c₁ c₂ c₃ . . . c_n-2 c_n-1 c_n

Meshing is the interchanging of the individual elements of each block code. For example,

a₁ b₁ c₁ a₂ b₂ c₂ a₃ b₃ c₃ . . . a_n-2 b_n-2 c_n-2 a_n-1 b_n-1 c_n-1 a_n b_n c_n

We have just scrambled the block codes into a form where each bit of a particular block is farthest away of another bit of the same block. Due to this property of Meshing burst errors have a lower probability of affecting any one particular block or codeword.

We shall define Meshing more formally. Consider any (n,k) linear block code C. Let B denote the data stream of C with m blocks or codewords and denote B_ij as bit j of codeword i . Meshing is defined as:

B₁₁ B₂₁ B₃₁ . . .B_m1 B₁₂ B₂₂ B₃₂ . . . B_m2 B₁₃ B₂₃ B₃₃ . . . B_m3 . . . B_mn

3. Programming Aspect: Burst Errors

In simulating burst error, the following programming code replaced the random error programming code in our encoding and decoding simulation program from above.

(* Simulating Burst errors *)

(* We define burst length the length where *)

(* the random errors can occur *)

burstlength=27;

(* Picks where the burst starts *)

(* One burst per data stream *)

starterror=Random[Integer,{burstlength,Length[encodeddatastream]-

burstlength}];

Do[

burst1[x]=Random[Integer,{starterror,starterror+burstlength}];

burst2[x]=Random[Integer,{starterror-burstlength,starterror}]

,{x,1,errorsinstream}];

(*Flips the bit in the data stream*)

Do[

If[(Part[encodeddatastream,burst1[iii]]==1),errelement=0,errelement=1];

If[(Part[encodeddatastream,burst2[iii]]==1),errelement=0,errelement=1];

encodeddatastream=ReplacePart[encodeddatastream,errelement,burst1[iii]];

encodeddatastream=ReplacePart[encodeddatastream,errelement,burst2[iii]]

,{iii,1,errorsinstream}];

Basically the user specifies the number of errors to incorporate into the data stream and the length of the burst error. The programming code randomly picks a bit in the data stream and randomly flips a specified number of bits within the length specified by the user.

4. Burst Error Control Simulations

The following program code processes the data using the Meshing technique prior to entering the channel of transmission (adding errors).

(*This is the modified encoding burst error control technique*)

encodeddatastream=Partition[encodeddatastream,n];

temp={0};

Do[

Do[

build=Part[encodeddatastream,i,j];

temp=Join[temp,{build}],{i,1,Length[encodeddatastream]}],{j,1,n}];

build=Delete[temp,1];

This programming code decodes the Meshing technique and recovers the original block codes after transmission or adding of errors.

(*Decoding process of mod tech burst control*)

encodeddatastream=Flatten[encodeddatastream];

numcodewords=Length[Partition[encodeddatastream,n]];

temp={0};

Do[

Do[

build=Part[encodeddatastream,numcodewords*i+j];

temp=Join[temp,{build}],{i,0,n-1}],{j,1,numcodewords}];

encodeddatastream=Delete[temp,1];

5. Results

The following data and graphs give evidence that the Meshing technique is truly more advantageous for burst error control than without it. As before, the following is a list of received transmissions for each error added in a burst.

(7,4)-code

Without Burst Error Control

"This is MtFn test!"

"This is mWUn test!"

"J( is a fun test!"

"This is a fun$.9T!"

"This is9jFun test!"

"T)|o&is a fun test!"

"This is a f\\qXest!"

"T:43is a fun test!"

"This 6i fun test!"

"This ixu=mfun test!"

"This is a fun UIi!"

"This iyw~yfun test!"

"ThoYs a fun test!"

"Thjg 8s a fun test!"

"This is fZPE test!"

"This is a biGNdest!"

"This is#NV§n test!"

"This is aHM< test!"

"This is a oL`$est!"

"Thip!'\.00a fun test!"

"This is a+N8ptest!"

(7,4)-code

With Burst Error Control

"This is i(fun |mst!"

"This is a fFn teCt!"

"Tiis is a fun test!"

"This is a fun tm{|!"

"This is a fx>py5#t!"

"This is a fuf(test!"

"This is a eFn test!"

"This )3 a fun tes|)"

"Tha{(is a fun test!"

"Tlms is a fun te{t!"

"This is a fun tes$!"

"This is a fun`tast!"

"This ip#a#fEn test!"

"This i~ lpk%n test!"

"This is a-k%> t5st!"

"Dhis is a fum#DepD"

"This is a 6x>}$e~$q"

"This is a fun desu!"

"TkiC is Q fun test!"

"This is e fun tewt!"

"T\ts is a fun t5st!"

(23,12)-code

Without Burst Error Control

"jA is a fun test!"

"ThbfK a fun test!"

"This is\.00gtun test!"

"This isx.fun test!"

"This is a fun te-r"

"T1P`[)s a fun test!"

"ThhvDs a fun test!"

"This is al7~ test!"

"Thmsk)j a fun test!"

"`is is a fun test!"

"Ta_ is a fun test!"

"This is a fv¶pCst!"

"T9Xj is a fun test!"

"T*8t is a fun test!"

"This is a lj?&¶est!"

"This-nl[! fun test!"

"Thfais a fun test!"

"This is a fun `HT!"

"This iq$\n&fun test!"

"This is a fun ~d#4!"

"This is oJfun test!"

(23,12)-code

With Burst Error Control

"This is a fun test!"

"This is a fun test!"

"Tais is a fun test!"

"Thi- is a fun test!"

"Vhis is a fun test!"

"This is a fun test!"

"TIs is a UnP4est!"

"This is0a fun tec}!"

"This is a fun test!"

"This h: a fun test!"

"Thb2 is a fun tet!"

"Th1v!s a fun test6"

"This is a oun test1"

"This is a fun test!"

"Tc)s is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fun test!"

"This is a fsl test!"

"This 9s a fun test!"

"ThYs is a fun!est!"

The graphs below demontrate burst errors in transmission with the Meshing technique and without. The graphs are viewed top to bottom with 52 to 57 errors in the bit stream.

(7,4)-code

Without With

Burst Error Control Burst Error Control

(23,12)-code

Without With

Burst Error Control Burst Error Control

Bibliography