|
Основные понятия
Ошибки в принятой кодовой комбинации можно обнаружить и исправить с помощью помехоустойчивого кода.
Коды реализуются для режимов обнаружения ошибок, исправления ошибок и одновременного обнаружения и исправления ошибок.
Корректирующие возможности кода определяются его избыточностью, понятие которой состоит в следующем [15,17].
Равномерный (простой) двоичный код имеет множество кодовых комбинаций B={bi}, мощность которых определяется как N=2n, где n - разрядность (длина) кода.
Для передачи сообщений из множества B выбирают по определенному закону подмножество AÌB мощностью M кодовых комбинаций, причем M<N. Эти M кодовых комбинаций объявляют разрешенными, а M-N кодовых комбинаций – запрещенными.
Избыточность кода оценивают по формуле
r=1-log2M/ log2N.
Множество A разрешенных кодовых комбинаций является помехоустойчивым кодом.
Аналогично можно ошибки записать в виде кодовых комбинаций, причем множество возможных ошибок E={ei} будет иметь мощность |E|=N, т.е. E=B.
Число ненулевых разрядов в кодовых комбинациях называется весом комбинации. Обозначим кодовую комбинацию через bi, а вес di этой кодовой комбинации – через w(di). Если bi=0101101, то w(di)=4.
Кратность ошибки равна весу комбинации ошибок ei.
Пусть передается кодовая комбинация aiÎA, а принимается кодовая комбинация biÎB, причем bi может принадлежать и не принадлежать множеству A. Кодовая комбинация bi есть результат воздействия ошибки на кодовую комбинацию ai, т.е. bi=aiÅ ei. Безошибочной будет передача в том случае, если bi=ai, т.е. w(ei)=0. При w(ei)¹0®bi¹ai и возможно, что biÎA - необнаруженная ошибка или biÏA - обнаруженная ошибка в принятой кодовой комбинации.
Идея обнаружения ошибок состоит в следующем.
Принятая кодовая комбинация декодируется автоматическим устройством – декодером. В результате декодирования принимается решение, содержит или нет кодовая комбинация ошибки. При этом проверяются условия: а) biÎA и biÏВ/A; б) biÎВ/A и biÏA. При выполнении условия б) считается, что кодовая комбинация содержит ошибку.
Очевидно, что возможно обнаружить те ошибки, которые переводят кодовую комбинацию ai в множество В/A, причем число этих комбинаций ошибок равно N-M. Остальные M комбинации ошибок не обнаруживаются, т.к. они переводят одну разрешенную кодовую комбинацию в другую кодовую комбинацию.
Пример. Пусть n=4. Множество простого кода В ={0000, 0001, 0010, 0011, 0100, …, 1111}. Выберем множество A по закону . Тогда множество A ={0011, 0101, 0110, 1001, 1010, 1100}, а множество В/A содержит оставшиеся комбинации из множества простого кода. Множество E = В. Пусть e =0110, a =1000, тогда при поразрядном суммировании e и a по модулю два получим b=aÅe= 1110. Так как кодовая комбинация biÎВ/A, то ошибка обнаружена.
Идея исправления ошибок состоит в следующем. Множество простого кода В разбивается на M=2m подмножеств Вi, причем |Вi|=2n-m. В каждое множество Вi входит одна разрешенная кодовая комбинация aiÎВi и (2n-m-1) запрещенных кодовых комбинаций.
При декодировании принятой кодовой комбинаций bi проверяется, какому из подмножеств Вj (j=1,1,…, 2n-m) принадлежит комбинация bi. Если biÎВj, то принимается решение, что передавалась кодовая комбинация aj. Исправляются все ошибки, в результате которых biÎВj, причем их количество 2n-m-1. Все остальные ошибки, которые “выводят” bi из множества Вj (biÏВj), не исправляются.
Пример. Множество простого кода В ={0000, 0001, 0010, 0011, 0100, …, 1111}. M=21, |Вi|=23-1=22=4. Построим множества В1 ={101, 001, 111, 100} и В2 ={010, 110, 011, 000}. Разрешенные кодовые комбинации 101 и 010.
Если ai =101 и e =111, то bj=aiÅe =010. Следовательно, ошибка не обнаружена.
Если ai =101 и e =001, то bj=aiÅe =100, ошибка обнаружена.
При построении кода решаются две задачи:
1) как выбрать множество А (задача кодирования);
2) как разбить множество В на подмножества Вi (задача декодирования).
Дата добавления: 2015-10-21; просмотров: 110 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Коды по законам комбинаторики | | | Коды для обнаружения одиночных ошибок |