2.10. Коды с обнаружением ошибок
Код с четным числом единиц
Код содержит лишь один избыточный символ. Выбирается избыточный символ таким образом, чтобы общее количество единиц в кодовой комбинации было четным. Проверка кодовой комбинации производится путем суммирования по модулю два всех его символов. Избыточность кода равна
где m – длина кодовой комбинации, r – число проверочных символов.
Код позволяет обнаруживать однократные ошибки и все ошибки нечетной кратности, так как только в этих случаях количество единиц в комбинации станет нечетным. Не обнаруживаются ошибки четной кратности.
Код с удвоением элементов
Код с удвоением элементов характеризуется введением дополнительных символов для каждого символа информационной части комбинации, причем единица дополняется нулем и преобразуется в 10, а нуль дополняется единицей и преобразуется в 01. Тогда исходная, например, комбинация 10101 будет представлена в виде 1001100110. Показателем искажения кода будет появление в «парных» элементах сочетаний вида 00 или 11. Избыточность кода не зависит от числа элементов кодовой комбинации и равна Кизб = 0,5. Код позволяет обнаруживать все ошибки, за исключением случаев, когда имеют место две ошибки в «парных» элементах.
Помехоустойчивость кода с удвоением элементов выше помехоустойчивости кода с четным числом единиц. Это достигнуто за счет увеличения избыточности кода и усложнения процедуры проверки кода.
Инверсный код
В основу построения инверсного кода положен метод повторения исходной кодовой комбинации. Причем в тех случаях, когда исходная комбинация содержит четное число единиц, вторая комбинация в точности воспроизводит исходную. Если же исходная комбинация содержит нечетное число единиц, то повторение производится в инвертированном виде. Например, комбинации 01010 и 01110 инверсным кодом представляются соответственно как 0101001010 и 0111010001.
Проверка кодовой комбинации производится в такой последовательности. Сначала суммируются единицы, содержащиеся в основной комбинации. Если их число окажется четным, то элементы дополнительной комбинации принимаются в неизменном виде. После этого обе комбинации сравниваются поэлементно (первый элемент с первым, второй со вторым и т. д.), и при обнаружении хотя бы одного несовпадения принятая комбинация бракуется.
Если же количество единиц основной комбинации нечетное, элементы второй комбинации принимаются в инвертированном виде. Затем, как и в предыдущем случае, основная и дополнительная комбинации сравниваются поэлементно.
Избыточность кода не зависит от числа элементов кодовой комбинации и равна Kизб = 0,5.
Код позволяет обнаружить практически все ошибки в комбинации. Ошибки не будут обнаружены лишь тогда, когда одновременно исказятся два, четыре и т. д. элемента в исходной комбинации и соответствующие два, четыре и т. д. элемента дополнительной комбинации.
Из рассмотренных кодов инверсный код обладает наибольшей помехоустойчивостью.
2.11. Коды с обнаружением и исправлением ошибок
Коды Хэмминга
Известно несколько разновидностей кода Хэмминга, обладающих различной корректирующей способностью. К этим кодам обычно относят коды с исправлением однократных ошибок и коды с исправлением однократных и обнаружением двукратных ошибок.
Код Хэмминга, обеспечивающий исправление всех однократных ошибок, должен иметь минимальное кодовое расстояние dмин = 3. Длина кода m выбирается из условия
2 k £ 2 m/(1 + m), (2.14)
где k – количество информационных (основных) разрядов.
Преобразовав (2.17) с учетом, что r = m – k получим
2 r ³ r + k +1 (2.15)
или
r = log2 (r + k + 1).
Код строится таким образом, чтобы в результате r = m – k проверок получить r -разрядное двоичное число, указывающее номер искаженной позиции кодовой комбинации.
Имея т = r + k разрядов, самокорректирующийся код можно построить следующим образом.
Присвоим каждому из разрядов свой номер от 1 до т, запишем эти номера в двоичной системе. Поскольку 2k > т, каждый номер можно представить, очевидно, r -разрядным двоичным числом. Для определенности будем полагать, что при записи номеров разрядов в двоичной системе использован позиционный способ изображения чисел с естественными весами разрядов; вообще это условие не является необходимым.
Предположим далее, что все т разрядов кода разбиты на контрольные группы (которые частично перекрываются), причем так, что единицы в двоичном представлении номера разряда указывают на его принадлежность к определенным контрольным группам.
Например, разряд № 5 принадлежит к 1-й и 3-й контрольным группам, потому что в двоичном представлении его номера
1-й и 3-й разряды содержат единицы; разряд № 7 принадлежит 1-й, 2-й и 3-й контрольным группам, потому что в двоичном представлении его номера
содержатся единицы в 1-м, 2-м и 3-м разрядах и т. д.
Среди т разрядов кода при этом имеется r разрядов, каждый из которых принадлежит только к одной контрольной группе. Это разряды, номера которых являются целыми степенями двойки и потому в двоичном представлении содержат по одной единице: разряд № 1, принадлежащий только к 1-й контрольной группе (потому что его номер в двоичной системе имеет вид (...000001)2 ), разряд № 2, принадлежащий только ко 2-й контрольной группе (так как (2)10 = (...000010)2 ), ..., разряд 2r -1, принадлежащий только к r -ой контрольной группе. Эти r разрядов мы и будем считать контрольными. Остальные k разрядов, каждый из которых принадлежит по меньшей мере к двум контрольным группам, будут основными разрядами числа (информационными разрядами).
При этом в каждой из r контрольных групп будем иметь по одному контрольному разряду. Например, в 1-ю контрольную группу входят все разряды, номера которых в двоичном представлении содержат единицу младшего разряда: 1-й, 3-й, 5-й, 7-й и т. д.; из них контрольным является 1-й разряд. Во 2-ю контрольную группу входят все разряды, номера которых в двоичном представлении содержат единицу 2-го разряда: 2-й, 3-й, 6-й, 7-й и т. д.; из них контрольным является 2-й разряд.
Таким образом, проверочные группы должны иметь вид
Содержимое основных k разрядов числа заранее задано: в них размещается передаваемая информация. В каждый из контрольных разрядов поместим такую цифру (0 или 1), чтобы общее количество единиц в его контрольной группе было четным. Так как каждый контрольный разряд принадлежит только к одной контрольной группе, цифры в контрольных разрядах не зависят друг от друга. Таким образом формируется код числа.
После приема кода производится контроль по четности отдельно в каждой контрольной группе. Если код был принят верно, то во всех контрольных группах количество единиц будет четным (сумма по модулю два будет равна нулю). Если в каком-либо разряде при передаче кода была допущена ошибка, то в тех контрольных группах, в которые этот разряд входит, количество единиц окажется нечетным (сумма по модулю два равна единице). Но любой разряд кода входит в те контрольные группы, которые соответствуют единицам в его номере, записанном в двоичной системе. Следовательно, по результатам контроля, проведенного внутри контрольных групп, можно судить о номере разряда, принятого неверно. Изменив значение этого разряда на противоположное, получим правильный код.