Коды БЧХ

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Математически полинома g(x) на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона

Коды Рида — Соломона — недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида-Соломона, работающие с байтами (октетами).

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов

Хотя  блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале сАБГШ), менее высока.

Свёрточные коды

Свёрточный  кодер ( )

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

Свёрточные  коды, как правило, порождаются дискретной линейной инвариантной во времени системой. Поэтому, в отличие от большинства блоковых кодов, свёрточное кодирование — очень простая операция, чего нельзя сказать о декодировании.

Кодирование свёрточным кодом производится с  помощью регистра сдвига, отводы от которого суммируются по модулю два. Таких сумм может быть две (чаще всего) или больше.

Декодирование свёрточных кодов, как правило, производится по алгоритму Витерби, который пытается восстановить переданную последовательность согласно критерию максимального правдоподобия.

Преимущества и недостатки свёрточных кодов

Свёрточные  коды эффективно работают в канале с белым шумом, но плохо справляются  с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование. Итеративное декодирование

Преимущества  разных способов кодирования можно  объединить, применив каскадное кодирование. При этом информация сначала кодируется одним кодом, а затем другим, в результате получается код-произведение.

Например, популярной является следующая конструкция: данные кодируются кодом Рида-Соломона, затем перемежаются (при этом символы, расположенные близко, помещаются далеко друг от друга) и кодируются свёрточным кодом. На приёмнике сначала декодируется свёрточный код, затем осуществляется обратное перемежение (при этом пачки ошибок на выходе свёрточного декодера попадают в разные кодовые слова кода Рида — Соломона), и затем осуществляется декодирование кода Рида — Соломона.

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако, декодирование требует больших ресурсов. К таким кодам относяттурбо-коды и LDPC-коды (коды Галлагера).

Оценка эффективности кодов

Эффективность кодов определяется количеством  ошибок, которые тот может исправить, количеством избыточной информации, добавление которой требуется, а также сложностью реализации кодирования и декодирования (как аппаратной, так и в виде программы для ЭВМ).

Энергетический выигрыш

При передаче информации по каналу связи вероятность  ошибки зависит от отношения сигнал/шум на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определённых системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения.

Поскольку помехоустойчивое кодирование позволяет исправлять ошибки, при его применении мощность передатчика можно снизить, оставляя скорость передачи информации неизменной. Энергетический выигрыш определяется как разница отношений с/ш при наличии и отсутствии кодирования.

Применение кодов, исправляющих ошибки

Коды, исправляющие ошибки, применяются:

• в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам.
• в системах хранения информации, в том числе магнитных и оптических.

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 9

1.Активные  методы защиты  информации от  утечки по техническим  каналам.

2.Коды  Хэмминга, Файра и  БЧХ.

1.Активные методы защиты информации от утечки по техническим каналам.

Приборы для постановки активной заградительной помехи

Эти приборы предназначены для защиты телефонных линий практически от всех видов прослушивающих устройств. Достигается это путем подачи в линию дополнительных сигналов (заградительной помехи) и изменения стандартных параметров телефонной линии (обычно в разумных пределах изменяется постоянная составляющая напряжения в линии и ток в ней) во всех режимах работы. Для того чтобы помехи не очень сильно мешали разговору, они компенсируются перед подачей на телефонный аппарат владельца. Во избежание неудобств для удаленного абонента помехи подбираются из сигналов, которые затухают в процессе прохождения по линии или легко фильтруются абонентским комплектом аппаратуры городской АТС. Для “хорошего” воздействия помехи на аппаратуру перехвата ее уровень обычно в несколько раз, а иногда и на порядки превосходит уровень речевого сигнала в линии.

Эти помехи воздействуют на входные каскады, каскады  АРУ, узлы питания аппаратуры перехвата, что проявляется в перегрузке входных цепей, в выводе их из линейного  режима. Как следствие, злоумышленник вместо полезной информации слышит в наушниках лишь шум.

Некоторые виды помех позволяют воздействовать на телефонные радиоретрансляторы таким  образом, что происходит смещение или “размывание” несущей частоты передатчика, резкие скачки частоты, искажения формы высокочастотного сигнала, перемодуляция или периодическое понижение мощности излучения. Кроме того, возможен “обман” системы принятия решения, встроенной в некоторые виды аппаратуры несанкционированного получения информации, и перевод ее в “ложное состояние”. В результате такие устройства начинают расходовать свои ограниченные ресурсы, например, звуковой носитель или элементы питания. Если в нормальном режиме такой передатчик работает периодически (только при телефонных переговорах), а автоматическая система регистрации включается только при наличии радиосигнала, то в этом случае она работает постоянно. В результате злоумышленнику приходится прибегать к услугам оператора для выделения полезной информации (если она осталась), что чаще всего нереализуемо.

Недостатки:

Постановщики  заградительных помех обеспечивают защиту телефонной линии только на участке от самого прибора, к которому подключается штепсель телефонного  аппарата, до городской АТС.

2.Коды Хэмминга, Файра и БЧХ.

Коды Хэмминга

Коды, предложенные Р. Хэммингом, обладают способностью обнаружить и исправить одиночные ошибки.

Предположим, что имеется код, содержащий m информационных разрядов и k контрольных разрядов. Запись на k позиций определяеется при проверке на четность каждой из проверяемых k групп информационных символов. Пусть было проведено k проверок. Если результат проверки свидетельствует об отсутствии ошибок, запишем 0, если есть ошибка - 1. Запись полученной последовательности символов образует двоичное число.

Свойство кодов Хэмминга таково, что контрольное число указывает номер позиции, где произошла ошибка. При отсутствии ошибки в коде данная последовательность будет содержать только нули. Полученное число описывает таким образом n=(m+k+1) событий. Следовательно, справедливо неравенство

Определить  максимальное значение m для заданого n можно из следующего:

Определим теперь позиции, которые надлежит проверить в каждой из k проверок. Если в кодовой комбинации ошибок нет, контрольное число содержит только нули. Если в первом разряде контрольного числа стоит 1, это означает, что в результате первой проверки обнаружена ошибка. Первая проверка охватывает позиции 1, 3, 5, 7, 9, ... (в двоичной записи этих чисел младший разряд равен 1). Вторая проверка - 2, 3, 6, 7, 10...

Для контроля будем использовать позиции 1,2,4,8,..., так как в данные позиции встречаются  только в одной проверяемой группе символов.

Примеры кодирования информации по коду Хемминга для семиразрадного кода: