GROUP (вторая лаба)
Описание файла
Файл "GROUP" внутри архива находится в следующих папках: 2, 102N. Текстовый-файл из архива "вторая лаба", который расположен в категории "". Всё это находится в предмете "вычислительные машины, системы и сети (вмсис)" из 5 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "вмсис" в общих файлах.
Просмотр текстового-файла онлайн
Возможно не удалось распознать кодировку файла
Лабораторная работа 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, ко-
торые составлены с помощью ЭВМ.