Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Помехоустойчивые коды

 

Основные понятия

 

Ошибки в принятой кодовой комбинации можно обнаружить и исправить с помощью помехоустойчивого кода.

Коды реализуются для режимов обнаружения ошибок, исправления ошибок и одновременного обнаружения и исправления ошибок.

Корректирующие возможности кода определяются его избыточностью, понятие которой состоит в следующем [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 | Нарушение авторских прав


Читайте в этой же книге: ВИДЫ МОДУЛЯЦИИ | Спектры сигналов, модулированных по амплитуде | Спектры сигналов, модулированных по частоте | Спектры сигналов, модулированных по фазе | Спектры манипулированных сигналов | Принципы построения многоканальных систем | Принцип действия канала с амплитудной манипуляцией | Принцип действия канала с частотной манипуляцией | Принцип действия канала с относительной фазовой модуляцией | Простой, безызбыточный код |
<== предыдущая страница | следующая страница ==>
Коды по законам комбинаторики| Коды для обнаружения одиночных ошибок

mybiblioteka.su - 2015-2024 год. (0.01 сек.)