# MATB24H3 Lecture Notes - Parity-Check Matrix, Hamming Weight, Generator Matrix

106 views9 pages

Published on 21 Apr 2013

Department

Mathematics

Course

MATB24H3

Professor

University of Toronto at Scarborough

Department of Computer & Mathematical Sciences

MAT B24S Fall 2011

MAT B24

Lecture 13.

1 Binary Linear Codes

In this application messages will be encoded using the binary alphabet {0,1}=

B.Bwill be used to create message words that will be encoded, transmitted,

received and then decoded.

The Hamming 7-4 code starts with ‘messages’ that have length 4 each

rep. a letter. i.e. all possible messages: 24= 16.

space 0000

A 0001

B 0010

C 0011

D 0100

E 0101

F 0110

G 0111

H 1000

I 1001

J 1010

K 1011

L 1100

M 1101

N 1110

O 1111

To simply send these is simple but if an

error occurs then it cannot be detected. i.e.

say message received is 1 which decodes to

the word BEAN but the correct message is

2

B E A N

1) 0010 0101 0001 1110

there is one mistake ↑and one ↑

B E E F

2) 0010 0101 0101 0110

There is one mistake in each of the words

0001 and 1110 which are not detectable.

We want to detect single-error transmissions and to correct, the error.

1

To do these we lengthen the words to have 7 characters where the last 3

‘check’ for errors. i.e. if x1, x2, x3, x4are the ﬁrst 4 characters and the last 3

are given by equations carefully chosen.

EXAMPLE:

x5=x1+x3+x4

x6=x1+x2+x3

x7=x2+x3+x4

in Z2

these chosen equation are called parity check equations. Now the question

remains: How do we choose these equations?

The above equations give the following codes in Z7

2for the possible mes-

sages in Z4

2

message code no.

0000 0000000 0

0001 0001101 1

0010 0010111 2

0011 0011010 3

0100 0100011 4

0101 0101110 5

0110 0110100 6

0111 0111001 7

1000 1000110 8

1001 1001011 9

1010 1010001 10

1011 1011100 11

1100 1100101 12

1101 1101000 13

1110 1110010 14

1111 1111111 15

The coded words are in Z7

2. The ﬁnal 3 characters are the parity-check

position of the message.

Deﬁnition: The Hamming weight of a word uis wt(u) = number of char-

2

acters equal to 1.

Example: If u= 0110100, v = 0101110 ﬁnd wt(u), wt(v).

wt(0110100) = 3 wt(0101110) = 4

Deﬁnition: If u, v are two words then let d(u, v) denote the number of

entries in uand vthat are diﬀerent call this the distance between uand v.

Example: If u= 0110100,v= 0101110,w= 1111111 ﬁnd d(u,v), d(v,w)

and d(u,w).

d(u,v) = 3 d(v,w) = 3 d(u,w) = 4

Deﬁnition: We add two words by adding corresponding characters in Z2.

Example: If u= 0110100,v= 0101110,w= 1111111 ﬁnd u+v,v+wand

u+w.

u+v= 0011010 v+w= 1010010 u+w= 1001011

NOTE wt(u+v) = d(u,v).

Now a single error can occur in any one of the 7 characters.

If uis send and u′is received with a single error then d(u, u′) = 1 or

wt(u+u′) = 1. To check for errors we check the parity check. If the code

words are at least 3 units apart then by looking to see the closest code word

to u′we can correct it. i.e. if u′= 0100110 is received

=⇒since we know

x5=x1+x3+x4

x6=x1+x2+x3

x7=x2+x3+x4

we know there is an error. We look and compare this to the rest of the code

words. For example the distance between u′and u1is:

d(u′,0001101) = 4

3

## Document Summary

In this application messages will be encoded using the binary alphabet {0, 1} : b will be used to create message words that will be encoded, transmitted, received and then decoded. The hamming 7-4 code starts with messages" that have length 4 each rep. a letter. i. e. all possible messages: 24 = 16. space. To simply send these is simple but if an error occurs then it cannot be detected. i. e. say message received is 1 which decodes to the word bean but the correct message is. There is one mistake in each of the words. We want to detect single-error transmissions and to correct, the error. To do these we lengthen the words to have 7 characters where the last 3. Check" for errors. i. e. if x1, x2, x3, x4 are the rst 4 characters and the last 3 are given by equations carefully chosen.