# GROUP_E

Посмотреть архив целикомTHE GENERAL and PROFESSIONAL EDUCATION MINISTRY

of the Russian Federation

_________

The MOSCOW POWER ENGINEERING INSTITUTE

__________________________________

Is authorized

By MPEI educational management

Laboratory exercises

At the subject

The information and coding theory

DESIGNING and IMPLEMENTATION of GROUP CODES

Moscow 1998

Laboratory exercises at the subject "The Theory of the information and encoding ". "

Designing and realization of the group codes ".. This edition is done by KUSHELEV

U.N., ZHAVORONKOV M.A. ,and SOROKIN P.

Laboratory exercises are carried out on PC and is a modernization of the Laboratory

exercises N102 (?????? ?.?., ?????? ?.?.,).

The laboratory exercises is intended for the students of all fields in a control and

computers. Duration of employment is 4 hours.

_________________

C the Moscow power engineering institute, 1998.

Laboratory exercises N 102

THE GROUP CODES DESIGNING and REALIZATION(IMPLEMENTATION)

The purpose of the exercises is both studying and mastering of principles to construct

the technical implementation of the coding and decoding devices for the group adjusting

codes.

The instructions to design of the group adjusting codes

Definition of the redundant symbols number

The designing of a specific adjusting code is made by taking into account demanded

volume of a code N, i.e. due to the necessary number of commands, discrete magnitude

of measurable value which should be transmitted, and/or to the most probable vectors of

any statistical errors in the used communication channel. We shall name a code

combination as an error vector the one having unit in the bits exposed to distortion, and

zero in all other bits. Any distorted code combination can be examined now as the sum

(or the difference) on the module two of legal code combinations and vector of an error.

Proceeding from inequalities 2K-1i N, we determine the number of the information

bits which is necessary to transfer the given number of commands by an usual binary

code.

To the each of the (2K-1) nonzero combinations of an unredundant K digit code we

should put into the conformity a combination from n symbols. The symbols magnitude in

the n-k verifying bits of the combination are established as a result of summation on the

module two the magnitude of symbols in the certain information bits.

We have to define a number of the verifying bits and the information bits numbers

which are included in the each equality for evaluation the verifying bits symbols.

From general number of (2n-1) probable errors the group code can correct only (2n-k-1)

versions of errors [I].

To have an opportunity to receive information of an error vector, which influences to

the received code combination, the each error vector subjected to an elimination should

be compared to some control sequence of symbols named identifier.

On the receiving side, the each identifier symbol will be defined as a result of one of

the parities fulfillment, which we have done for definition of the verifying symbols

magnitude at an encoding procedure.

In a group code the value of verifying symbols are selected so that the sum on the

module two for all symbols (including verifying ones), incorporated in the each of

parities, was equated to zero. In such case, the number of units among these symbols is

an even. Therefore the operations of symbols identifier definition are named as an even

parity check. At an absence of any errors it is formed an identifier, consisting exclusively

from zeroes, as a result of the parity checks. If the verifying equality is not satisfied, then

there is a unit in the appropriate bit of the identifier. Any correction of errors can be

possible only at the presence of the mutually unequivocal conformity between sets of the

identifiers and the total set of errors versions subjected to a correction.

Thus, the amount of errors subjected to a correction is determining by a choice of the

redundant symbols n-k number. The last ones should be enough to ensure the necessary

number of identifiers.

If, for example, we want to correct all single independent errors, then to a correction

is subjected the n errors.

000...01

000...10

.............

100...00.

The number of various nonzero identifiers should be not less than n. Hence, the

necessary number of the verifying bits should be determined from a ratio

(2n-k-1) i ?n1 =n.

Generally, for correction of all independent errors of a multiplicity up to t inclusively

we get

(2n-k-1) i ?n1+ ?n2+ ......+ ?nt.

We should to emphasize, that for the given inequality is underlined the theoretical

limit of minimally probable number of verifying symbols which is far from being done

practically in the all cases.

The drawing up procedure of the identifier's table

Let's begin, for simplicity, from an establishment of the identifiers for a case of the

single errors correction. Suppose, we should to code 15 commands. Then k = 4, n = 7.

Three redundant bits allow to use as an identifier three-digit binary sequences. Basically,

they can be compared to the errors subjected to a correction in any order. However, it is

more expedient to compare them to the errors in bits, since younger, in ascending order

of binary numbers.

Table 2.1

N of bit vector of identifier

number an error

1 0000001 001

2 0000010 010

3 0000100 011

4 0001000 100

5 0010000 101

6 0100000 110

7 1000000 111

By such comparison, the each identifier represents the binary number indicating the

bit, in which there was an error.

The codes, in which identifiers are established by the specified principle, are known

as Hamming codes.

Let's take now the more complex case of all single and double independent errors

correction. As an identifier of the single errors in the first and second bits we can accept

as well as it was done earlier the combinations 0...001 and 0...010.

The vector 0...011, subjected to an error correction, can be considered as a result of

the total influence of the two error vectors 0...010 and 0...001 and, hence, it should be

compared with an identifier, representing the sum on the module two of the identifiers

for these errors, i.e. 0...011.

To the vector of an error 0...01000 we should compare the identifier 0...0100 etc.

-------------------------------------------

Choosing a combination with number of bits less than i as an identifier for an isolated

error in the i-th bit, one should be convinced that there are used identifiers each of it is

different from the ones already used for all other vectors subjected to an errors correction

and having units in i-th or more younger bits. As a result we have:

Vector of identifier Vector of identifier

an error an error

00000001 000001 00001010 001010

00000010 000010 00001100 001100

00000011 000011 00010000 001111

00000100 000100 00010001 001110

00000101 000101 00010010 001101

00000110 000110 00010100 001011

00001000 001000 00011000 000111

00001001 001001 00100000 010000

By such way, it is possible to produce the table of identifiers for the given type of

error vectors with any number of bits.

As identifiers of the errors having units in a few bits there are established as the sum

on the module two of the single error identifiers in these bits, for a definition of the code

designing rules and the comparison of the verifying equalities it is enough to know only

identifiers of single errors for each of the bits.

For designing of the codes correcting binary independent errors, there are shown in

tab. 2.2, 2.3, 2.4 the packs of errors having two or three distorted symbols and identifiers

of the errors in the bits, which are made with the help of PC.

Table 2.2 Table 2.3

Code correcting a double Code, correcting packs in

independent errors two and less symbols

N of the bit identifier N of the bit identifier

1 0000001 1 00001

2 0000010 2 00010

3 0000100 3 00100

4 0001000 4 01000

5 0001111 5 01101

6 0010000 6 00111

7 0100000 7 01110

8 0110011 8 10000

9 1000000 9 10000

Table 2.4

Code, correcting a packs in

Three and less symbols

N bit number identifier

1 0000001

2 0000010

3 0000100

4 0001000

5 0010000

6 0100000

7 0001001

8 0010010

9 0100100

10 1000000

Definition of a verifying equality

Using the table of single error identifiers in each of the bits, it is easy to define, what

symbols of the bits should enter into the each of a parity check on.

Let's take as an example of tab. 2.1 identifiers for codes intended to correct the single

errors.

Basically, it is possible to design a code, truncating this table at any level. However,

there will be the optimum codes, which suppose the greatest number of information

symbols, among the codes having the same number of verifying symbols. For example,

code (7,4)

n = 7, k = 4.

Let's truncate this table at the 7-th bit and we shall find the numbers of bits, which

symbols should enter the each of a verifying equality.

Let's assume, that it will be found the unit at the first check on parity for the identifier

younger bit. Obviously, it can occur by a consequence of an error in one of the bits,

identifiers of which have a unit in the younger bit. Hence, the first verifying equality

should include symbols of the 1-st, 3-rd, 5-th ,and 7-th bits

?1 + ?3 + ?5 + ?7 = 0.

Unit in the second bit of the identifier can be a consequence of an error in the bits

, Identifier s which have unit in the second bit . From here, the second verifying

equality should look like

?2 + ?3 + ?6 + ?7 = 0.

Similarly, we find the third equality

?4 + ?5 + ?6 + ?7 = 0.

There are three verifying bits in our disposal that these equality were satisfied at an

absence of errors and for any magnitude of information symbols in a code combination.

We have to choose the numbers of these bits so, that each of them is entered only into

one of the equalities. It will ensure unequivocal definition of the symbols magnitude in

the verifying bits at coding. To the specified condition satisfy the bits, the identifiers of

which have on one unit. In our case it there will be the first, second and fourth bits.

Thus, the rules of a code designing have a form, i.e. the ratio were verified at the

coding procedure for a single error correcting code (7,4).

?1 = ?3 + ?5 + ?7 ;

?2 = ?3 + ?6 + ?7 ;

?4 = ?5 + ?6 + ?7 ;

?8 = ?1 + ?2 +?3 + ?4 + ?5 +?6 + ?7 ;

dm i r+ 1, d i 2s+1

The introduction of the verifying bit, ensuring the even number of units in all code

combination, allows to make a code (8,4) a8 = Sai mod 2 which is capable,

simultaneously, to correct the sole errors and find out the double ones.

Using the table of identifiers (tab. 2.2) and discussing likewise one can design the

verifying equality for any code correcting the single and double independent errors. For

example, for a code (8,2), turning out by truncation of this table on the 8-th bit, we shall

find the following parities, which should be fulfilled at the decoding and coding

procedures

?1 + ?5 + ?8 = 0 ?1 = ?5 + ?8

?2 + ?5 + ?8 = 0 ?2 = ?5 + ?8

?3 + ?5 = 0 ?3 = ?5

?4 + ?5 = 0 ?4 = ?5

?6 + ?8 = 0 ?6 = ?8

?7 + ?8 = 0 ?6 = ?8

Majority decoding of group codes

The majority decoding is based on the system of verifying equalities. The system

should be solved consecutive by each of independent variable, and by virtue of

redundancy it can be done by a few ways.

Any symbol ai is expressed by

combinations of other symbols. Thus, there can be used the trivial check ai = ai . The

results of calculations are applied to the majority element, appropriate to this symbol.

The last represents the circuit having

when is exited more than half of inputs. If the errors are absent, the verifying equality are

fulfilled and on an output of a majority element we get a true value of a symbol. If

number of inspections d> 2S + 1, then the presence of an error by multiplicity S and less

results in infringement of no more than S inspections. Therefore the correct decision can

be accepted on the majority of the undistorted inspections. For the specified condition

was carried out, any other symbol (not checked) should enter only into one verifying

equality. In this case we deal with the system of the divided inspections.

Let's construct systems of the divided inspections for decoding of the information

symbols considered before for a group code (8,2). As the code is designed for correction

of any double errors, the number of verifying equality for the each symbol defining

should be not less than 5. By substituting in equality 1 and 2 the value a8, received from

equality 5 and 6, and by writing down them due to a5, together with equalities 3 and 4

and trivial equality a5 = a5 we shall get system of the divided checks for a symbol and 45

0. Similarly we receive system of the divided inspections and for a symbol a8

?5 = ?6 + ?1 ?8 = ?3 + ?1

?5 = ?7 + ?2 ?8 = ?4 + ?2

?5 = ?3 ?8 = ?6

?5 = ?4 ?8 = ?7

?5 = ?5 ?8 = ?8 .

The software specification

At start of the program there are two windows from the menu. In one window presents

stages of the program operations, in the other one a designation of codes. At first we

choose a code.

The first stage of the laboratory exercises is drawing up of the equations. For drawing

up of the decoding equations it is necessary, using by the table, to enter numbers of the

bits consistently without blanks. For drawing up of the coding equation to enter numbers

of the verifying bits.

After the equations are drawing up the information combination is coded. For this

purpose the any magnitude of the information bits are entered. For input of the verifying

bits it is necessary to use the equation of coding.

The second stage is an assemblage of the circuit. On Fig.1 is submitted the circuit of

installation for the codes (7,4) implementation. For the appropriate signals application to

the information symbols, it is necessary to establish correctly connections with the

module two adders inputs of the coding devices with the help of keys "ENTER" and

blank. Further with the help of the same keys to supply correctly a signal on the module

two adders inputs, concerning already to the decoding device.

The third stage is a modeling. The magnitude of information symbols are established

by the student at a stage of the equations drawing up and by a program are moved on to

the module two adders inputs of the coding devices. The generated code combination is

displayed on the screen. Further it is directed to the communication channel, where the

combination symbols change is made for reflecting probable distortions of symbols in the

communication channel at influence of distortions. The deformed code combination also

is displayed on the screen.

There are determined identifier of an error according to the equation of decoding by a

means of the module two adders used into the decoding device.

In the each correcting code there is a unequivocal ratio between the set of identifiers

and the set of error vectors. The maintenance of such conformity is reached by means of

the decoder outputs connection with inputs of the correction vector formation block

consisting of the OR circuits complex (adjusting logic).

The deformed information symbols are corrected in the block of correction. The

accepted code combination also is displayed on the screen.

The adjusting logic provides blocking the acting message in case of an incorrigible

error presence(code 8,4). A signal of a repeated transfer inquiry is simultaneously

formed.

For other codes, the circuits differ in length of the data word, length of a code word

and the quantity of the module two adders. The assembly of the circuits and modeling

occurs as well as for a code (7,4).

The assignment

A. Is carried out by home preparation

1. Will familiarize with principles of group codes designing.

2. Using tab. 2.1, 2.2, 2.3, 2.4 to make the equations of coding and decoding for

codes:

(7,4), ensuring correction of single errors;

(8,4), ensuring correction of single errors and simultaneous detection of double errors;

(7,3), ensuring correction of double adjacent errors;

(8,2), ensuring correction of double independent errors;

(9,3), ensuring correction of errors packs in three and less symbols.

3. To code the specific sets of information symbols given personally to the each

student by the teacher, for codes specified in item 2.

4. For specific vectors of errors (till three for each code), chosen by the student from

all set of the probable errors to define the errors identifiers.

B. Is carried out in laboratory

1. Will familiarize with the specification of the software and circuit submitted on

Fig.1

2. Through special commands to enter in a department network

And to start on performance the program elen _ grk.exe.

3. To begin performance of laboratory exercises from a code (7,4) and during

modeling to look after process of the error's correction.

4. To execute item 2 for a code (8,4).

5. To execute laboratory exercises for a code (8,2) only for the versions of errors,

given by the teacher. To look after process of error's correction.

6. To execute item 4 for codes (7,3) and (9,3).

The requirements to the report

The report should include:

1. Equation of coding and decoding of codes specified in item 2 of the task.

2. Set of the code combinations appropriate to given information symbols, on each of

codes.

3. Set of the error's identifier appropriate to given vectors of errors, on each of codes.

4. Circuit of coding and decoding for one of codes, specified in item 2, and the reports

should contain the circuits of all researched codes implementation.

Control questions

1. What is the mathematical structure of a group code?

2. How the table of identifiers is made?

3. In what is the essence of majority decoding?

4. How the equations of coding and decoding are determined?

5. How to design a code, correcting single and simultaneously finding out a double

errors?

6. How to design a code which is finding out four-multiple errors?

7. How to design a code which is finding out threefold errors?

### Случайные файлы

Файл |

ПРОЧТИ (пароль).txt |

descript.txt |

Readme.txt |

describt.ion.txt |

questions.txt |