Экспериментальная отработка космических летательных аппаратов - Афанасьев В.А.
ISBN 5-7035-0318-3
Скачать (прямая ссылка):
В качестве корректирующих кодов наибольшее распространение получили так называемые групповые и циклические коды.
Групповые коды имеют т информационных и г проверочных символов {(ау•, ау,..., <ц/, , Ьу ,..., *гу-)} , у = 1 + 2п и обозначаются как (л, г)-коды.
Проверочные символы Ьу кодовых комбинаций формируются из информационных на основании выражения
Ьу= спау® сфу® ...ес1тат/ .
Здесь коэффициенты сц ,с#,...,б 0,1 и индивидуальны для
каждого 1-го проверочного разряда.
К числу групповых относится (7,4)-код Хэмминга. В этом коде проверочные символы располагаются на позициях 2°,21,22,...,2'1~1 кодового слова начиная слева (табл. 4.3), а информационные — на оставшихся позициях 3,5,6,7, причем младший информационный разряд располагается справа.
Таблица 4.3
КОДИРОВАНИЕ КОДОМ ХЭММИНГА
Информационная часть Результат кодирования кодом Хэмминга Дополнительный разряд
аА аз аг а\ *М Ьг аА *з аз аг а\ Ьа
1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 1 0 0 1 0
0 0 1 0 0 1 0 1 0 1 0 1
0 0 1 1 1 0 0 0 0 1 1 1
327
Окончание табл. 4.3
Информационная часть Результат кодирования кодом Хэмминга Дополнительный разряд
04 аз аг а\ Ь\ Ьг Ьз аз аг а\ Ьа
0 1 0 0 1 0 0 1 1 0 0 1
0 1 0 1 0 1 0 0 1 0 1 1
0 1 1 0 1 1 0 0 1 1 0 0
0 1 1 1 0 0 0 1 1 1 1 0
1 0 0 0 1 1 1 0 0 0 0 1
1 0 0 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 1 0 1 0 0
Значения коэффициентов сц , с%;.. •, с1Г определяются в соответствии со значением 1-го разряда двоичного числа / — номера позиции информационных символов. В данном случае / = 3, 5, 6, 7. Если двоичный эквивалент / содержит I в /-м разряде, то коэффициент равен 1. В противоположном случае он равен 0.
Так, для Ьу спшС1з-С14-1, а с^О, поскольку а\ > а3 , а4 расположены на позициях 7,5,3, а двоичные номера этих позиций (111), (101), (011) содержат в 1-м разряде 1, а двоичный номер а2 , расположенного на позиции 6, (ПО), содержит в 1-м разряде 0.
Рассуждая аналогично, получим с21 = с22 = ^24 = 1 ; с2з = 0; с31 = с32 = сзз= 1;с34 = 0- Таким образом, Ьу = ау® а^Ф ац\ Ьу = ау Ф ау Ф ; Ьу = ау Ф ау Ф ау.
В соответствии с этим правилом проставлены значения проверочных разрядов кода Хэмминга в табл. 4.3.
Значения информационных разрядов приведены в первом столбце. При приеме кодовых комбинаций осуществляется г проверок по отмеченному правилу с добавлением соответствующего контрольного разряда:
Пх = Ьу Ф ау Ф ау Ф ац ; П2 = Ьу Ф ау Ф ау Ф а^ ; П3 = Ьу Ф ау Ф ау Ф ау .
328
При отсутствии искажений двоичное число П = (П3П2П!) = (000). При искажении одного символа двоичное число П^Пз^П]) однозначно укажет позицию искажаемого разряда, который может быть исправлен. Данный код имеет d я 3 и позволяет исправлять однократные ошибки.
Например, при искажении а3 результат проверок П « (101), что соответствует 5-й позиции слова, в котором расположен а3 . Введение в код дополнительной позиции 8 для проверки на четность всего слова увеличивает d до четырех и позволяет обнаруживать две и исправлять одну ошибку.
Циклические коды относятся к блочным, систематическим, равномерным кодам. Совокупность кодовых комбинаций циклического ( л, г ) кода может быть получена на основании образующего полинома г -й степени 5(х), в качестве которого выбирается неприводимый полином с фиктивной переменной х°~ \ :
S(x) = X? + с^У"1 + ... + С\ХХ + 1 , С/ € { 0 , 1 } .
Полином S(x) может быть представлен в виде двоичного числа.
Например, полиному 3-й степени т? + х1 + 1 соответствует комбинация 1011. Примеры неприводимых полиномов и их двоичных эквивалентов даны в табл. 4.4.
Таблица 4.4
ОБРАЗУЮЩИЕ ПОЛИНОМЫ
Неприводимый полином Двоичный эквивалент полинома Число ненулевых членов
JC+ 1 111 3
х3 + X + 1 1011 3
х3+ х* + 1 1101 3
*4+ х+ 1 10011 3
хА+ х3+ 1 11001 3
хА+ х?+ х*+ X + 1 11111 5
я5**2* 1 100101 3
329
Окончание табл. 4.4
Неприводимый полином Двоичный эквивалент полинома Число ненулевых членов
х*+ х*+ 1 101001 3
х5 + х*+ х*+ х + 1 101111 5
х5+хА+х2+х+ 1 110111 5
х*+ х4+ х3+ х*+ 1 111011 5
X5+ х4+ х3* х* + 1 111101 5
х6+ х + 1 1000011 3
хЧхЧ 1 10001001 3
Чтобы закодировать двоичное сообщение h(x) циклическим кодом S(x), необходимо разделить многочлен х^ Л(х) на 5(х) и прибавить остаток от деления R(x) к многочлену х*• h(x) .
Тогда полученный многочлен к(х) = xfh(x) + R(x) при делении на S(x) будет давать остаток, равный нулю. Многочлен к{х) представляет результат кодирования сообщения h{x) кодом S(x) .
Если при передаче произойдет искажение, т.е. к(х) обратится в многочлен к*(х) , то при декодировании — делении к*(х) на S(x) — будет получен остаток R(x), не равный нулю при условии, что произошла обнаруживаемая ошибка. Его значение будет однозначно соответствовать искаженным символам кодовой комбинации, если кратность ошибки удовлетворяет кодовому расстоянию данного кода
Для обнаружения однократных и двукратных ошибок выбор полинома может быть произведен на основании следующих соотношений: п< 2Г- 1 при г> 3.
При выборе полинома S(x) степени г для исправления однократных ошибок справедливо соотношение
