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 various independent ways through the
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 inputs and one output, on which there is unit,
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?







Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.