Лабораторная работа: вторая лаба

Возможно не удалось распознать кодировку файла

Лабораторная работа n 102

ПОСТРОЕНИЕ И РЕАЛИЗАЦИЯ ГРУППОВЫХ КОДОВ

Целью работы является усвоение принципов построения и

технической реализации кодирующих и декодирующих устройств

групповых корректирующих кодов.

Указания к построению кодов

Определение числа избыточных символов

Построение конкретного корректирующего кода производится

исходя из требуемого объема кода n , т.е. необходимого числа

передаваемых команд или дискретных значений измеряемой величи-

ны и статистических данных о наиболее вероятных векторах оши-

бок в используемом канале связи. Вектором ошибки будем назыв-

ать кодовую комбинацию , имеющую единицу в разрядах, подверга-

ющихся искажению, и нули во всех остальных разрядах. Любую ис-

каженную кодовую комбинацию можно рассматривать теперь как

сумму (равно как и разность ) по модулю два разрешенной кодо-

вой комбинации и вектора ошибки.

Исходя из неравенства 2 5к 0-1 n, определяем число инфор-

мационных разрядов, необходимое для передачи заданного числа

команд обычным двоичным кодом.

Каждой из 2 5к 0-1 ненулевых комбинаций К-разрядного безизбы-

точного кода нам необходимо поставить в соответствие комбина-

цию из n символов. Значения символов в n-к проверочных разря-

дах такой комбинации устанавливаются в результате суммирования

по модулю два значений символов в определенных информационных

разрядах.

Нам подлежит определить число проверочных разрядов и но-

мера информационных разрядов, входящих в каждое из равенств

для определения символов в проверочных разрядах.

Из общего числа 2 5n 0-1 возможных ошибок групповой код может

исправить всего 2 5n-к 0-1 разновидностей ошибок [i].

Чтобы иметь возможность получить информацию о векторе

ошибки, воздействию которого подверглась полученная кодовая

комбинация, каждому вектору ошибки, подлежащей устранению,

должна быть сопоставлена некоторая контрольная последователь-

ность символов, называемая опознавателем.

Каждый символ опознавателя на приемной стороне будет оп-

ределяться в результате проверки одного из равенств, которые

мы составим для определения значений проверочных символов при

кодировании.

В групповом коде значения проверочных символов подбирают-

ся так, чтобы сумма по модулю два всех символов (включая про-

верочный), входящих в каждое из равенств, равнялась нулю. В

таком случае число единиц среди этих символов четное. Поэтому

операции определения символов опознавателя называют проверками

на четность. При отсутствии ошибок в результате всех проверок

на четность образуется опознаватель, состоящий из одних нулей.

Если проверочное равенство не удовлетворяется, то в соответс-

твующем разряде опознавателя появляется единица. Исправление

ошибок возможно лишь при наличии взаимно однозначного соот-

ветствия между множеством опознавателей и множеством подлежа-

щих исправлению разновидностей ошибок.

Таким образом, количество подлежащих исправлению ошибок

является определяющим для выбора числа избыточных символов

n-к. Последних должно быть достаточно для того, чтобы обеспе-

чить необходимое число опознавателей.

Если, например, мы желаем исправлять все одиночные неза-

висимые ошибки, то исправлению подлежит n ошибок

000...01

000...10

........

100...00.

Различных ненулевых опознавателей должно быть не менее n.

Необходимое число проверочных разрядов, следовательно,

должно определяться из соотношения

2 5n-к 0-1> С 51 0 =n.

В общем случае для исправления всех независимых ошибок

кратности до t включительно получаем

2 5n-к 0-1> С 51 0+ С 52 0+...С 51 0.

Стоит подчеркнуть, что в приведенных соотношениях указы-

вается теоретический предел минимально возможного числа прове-

рочных символов, которых далеко не во всех случаях можно реа-

лизовать практически.

Составление таблицы опознавателей

Начнем для простоты с установления опознавателей для слу-

чая исправления одиночных ошибок. Допустим, необходимо закоди-

ровать 15 команд. Тогда к=4, n=7. Три избыточных разряда поз-

воляют использовать в качестве опознавателей трехразрядные

двоичные последовательности. В принципе они могут быть сопос-

тавлены подлежащим исправлению ошибкам в любом порядке. Однако

более целесообразно сопоставлять их ошибкам в разрядах , начи-

ная с младшего, в порядке возрастания двоичных чисел.

Таблица 2.1

n разряда Вектор ошибки Опознаватель

1 0000001 001

2 0000010 010

3 0000100 011

4 0001000 100

5 0010000 101

6 0100000 110

7 1000000 111

При таком сопоставлении каждый опознаватель представляет

собой двоичное число, указывающее номер разряда, в котором

произошла ошибка.

Коды, в которых опознаватели устанавливаются по указан-

ному принципу, известны как коды Хэмминга.

Возьмем теперь более сложный случай исправления всех

одиночных и двойных независимых ошибок. В качестве опознавате-

лей одиночных ошибок в первом и втором разрядах можно принять,

как и ранее две комбинации 0...001 и 0...010.

Подлежащий исправлению вектор ошибки 0...011 может расс-

матриваться как результат суммарного воздействия двух векторов

ошибок 0...010 и 0...001 и , следовательно, ему должен быть

сопоставлен опознаватель, представляющий собой сумму по модулю

два опознаватель этих ошибок, т.е. 0...011.

Вектору ошибки 0...01000 сопоставляем опознаватель

0...0100 и т.д. Выбирая в качестве опознавателя единичной

ошибки в i-м разряде комбинацию с числом разрядов меньшим i,

необходимо убедиться в том, что для всех остальных подлежащих

исправлению векторов ошибок, имеющих единицы в i-м и более

младших разрядах, используются опознаватели, отличные от уже

использованных. В результате имеем:

Вектор ошибки Опознаватель Вектор ошибки Опознаватель

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

Таким путем можно получить таблицу опознавателей для век-

торов ошибок данного типа с любым числом разрядов.

Поскольку опознаватели векторов ошибок с единицами в нес-

кольких разрядах устанавливаются как суммы по модулю два опоз-

навателей одиночных ошибок в этих разрядах, то для определения

правил построения кода и сопоставления проверочных равенств

достаточно знать только опознаватели одиночных ошибок в каждом

из разрядов.

Для построения кодов, исправляющих двоичные независимые

ошибки, пачки ошибок из двух или трех символов и опознаватели

ошибок в каждом из разрядов сведены в табл. 2.2, 2.3, 2.4, ко-

торые составлены с помощью ЭВМ.

Возможно не удалось распознать кодировку файла

Возможно не удалось распознать кодировку файла

The operation instruction.

The basic opportunities:

1. Clear way to set and correct of the circuits.

2. The real modeling of the processes allows to study all features of the

circuit operation.

3. The processing and transfer of signals are divided,

that allows to study precisely the transfer of each signal .

4. Help file is available at an operational time.

The procedure:

1. To assemble the circuit (7,4).

2. To test it for diferent signs and vectors of an errors,

Correct the circuit if necessary.

3. Repeat items 1 and 2 for codes (7,4), (8,4), (7,3), (8,2)

(9,3).

The access to all opportunities of the program is carried out through

the main menu.

The circuit design (x, x):

On the screen the assemlage of the circuit is displayed. You are offered to

connect the elements. The current connection is displayed by a red

dashed line, it can be moved by cursor sign. The keys <BLANK> or <ENTER>

allow to fix connection or to remove it (if it was established).

At the end of the circuit design, press <ESC>, check up once again

correctness of the circuit, and press any key for the exrsices continuation.

The circuit operation (x, x):

Enter a code and vector of an error.

They are entered as a sequence of signs '0' and '1'.

For performance of the next step press any key.

After the modelling is over the table of the results is given out.

About the group codes:

You can overlook the text containing the information on ways of coding.

With viewing the standard keys are used.