Что такое избыточный код

автор: admin
05.07.2023

6.9.Избыточные коды и принципы использования избыточности

Одним из наиболее важных требований, предъявляемых к системам передачи информации, является обеспечение высокой достоверности принимаемых сообщений.

Вероятность ложного сообщения в данных системах, как правило, не должна превышать Р =10 -6 10 -9 , в то время как вероятность ошибочного приема единичного элемента в современных дискретных каналах редко бывает меньше Р=10 -3 10 -4 . Поэтому для повышения достоверности принимаемых сообщений обычно применяют специальные меры, снижающие вероятность появления ошибок до некоторого допустимого уровня.

Избыточные коды— одно из наиболее эффективных средств обеспечения высокой достоверности передаваемых и принимаемых сообщений. При построении избыточного кода для передачи информации используется лишь часть кодовых комбинаций (разрешенныекомбинации), отличающихся друг от друга более чем в одном разряде. Все остальные комбинации не используются и относятся к числузапрещенных. Это значит, что изnсимволов кодовой комбинации для передачи информации используетсяkсимволов. Следовательно, из общего числаN=2 n возможных кодовых комбинаций для передачи информации используется толькоNр=2 k разрешенных комбинаций. В соответствии с этим все множествоN=2 n возможных кодовых комбинаций делится на две группы. В первую группу входит множествоNр=2 k разрешенных комбинаций. Вторая группа включает в себя множество (N-Np)=2 n -2 k запрещенных комбинаций. Нетрудно видеть, что при использовании избыточных кодов ошибка в одном разряде приводит к замене разрешенной комбинации запрещенной. При достаточно большом отличии разрешенных комбинаций друг от друга можно обнаружить двукратную, трехкратную и т. д. ошибки, поскольку они приведут к образованию запрещенных комбинаций, а переход одной разрешенной комбинации в другую происходит под действием ошибок более высокой кратности.

Пример.Для передачи информации используются следующие кодовые комбинации, различающиеся не менее чем двумя разрядами: 0011, 0110, 1001, 1010, 1111, 0101, 0000. Пусть при передаче комбинации (например, 0011) произошла одиночная ошибка, в результате чего исказился первый разряд и принята комбинация 1011. Эта комбинация является запрещенной, что свидетельствует о наличии в ней ошибки. При выборе разрешенных комбинаций, отличающихся четырьмя разрядами 1100 и 0011, легко убедиться, что в этом случае обнаруживаются одно-, двух- и трехкратные ошибки и не обнаруживается лишь четырехкратная ошибка.

Искажение информации в процессе передачи сводится к тому, что некоторые из переданных символов заменяются неверными. Поскольку каждая из 2 k разрешенных комбинаций в результате действия помех может трансформироваться в любую другую, всего имеетсяNpN=2 k *2 n возможных случаев передачи (рис.6.10), включающих в себяNp=2 k случаев безошибочной передачи (рис.6.10, сплошные линии);Np(Np—1)=2 k (2 n —1) случаев перехода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам (рис.6.10, пунктирные линии);Np(N—Np)=2 k (2 n —2 k ) случаев перехода в запрещенные комбинации, которые могут быть обнаружены (рис. 6.10, штрих пунктирные линии).

Следовательно, не все искажения могут быть обнаружены. Доля обнаруживаемых ошибочных комбинаций:

Np(N—Np) / (NpN) = 1-Np/N= 1-2 k /2 n .

Для использования данного кода в качестве исправляющего множество запрещенных кодовых комбинаций разбивается на Npнепересекающихся подмножествMk.

Каждое из подмножеств ставится в соответствие одной из разрешенных комбинаций. Если принятая запрещенная комбинация принадлежит подмножеству Mi,считается, что передана комбинацияAi(рис. 6.10).

Рис.6.10 Возможные трансформации разрешенных кодовых комбинаций

шибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из комбинацииAi.

Таким образом, ошибка исправляется в (N—Np) случаях. Доля исправляемых ошибочных комбинаций

(N-Np) / Np(N—Np) = 1- Np.

Любой код при выполнении условия Np< N может применяться в качестве исправляющего. Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться данным кодом.

Пример.Определить долю обнаруживаемых ошибок кода, каждая комбинация которого содержит всего один избыточный символn= (k+ 1). Общее число возможных кодовых комбинаций составляет 2 k +1 =2 k *2, т.е. вдвое больше общего числа разрешенных комбинаций. За подмножество разрешенных кодовых комбинаций можно принять подмножество 2 k комбинаций, содержащих четное число единиц (или нулей). При кодировании к каждой последовательности из k информационных символов добавляется один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Искажение любого нечетного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Доля обнаруживаемых ошибок составляет 1 — 2 k /(2 k +1 ) = 0,5.

Большинство разработанных кодов предназначено для корректирования взаимно независимых ошибок определенной кратности и пачек (пакетов) ошибок.

Избыточное кодирование

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

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

Содержание

Способы борьбы с ошибками

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

В системах связи возможны несколько стратегий борьбы с ошибками:

обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;
обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
исправление ошибок (forward error correction) применяется на физическом уровне.

Коды обнаружения и исправления ошибок

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

Для этого при записи (передаче) в полезные данные добавляют специальным образом структурированную избыточную информацию (контрольное число), а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.

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

В действительности, используемые коды обнаружения ошибок принадлежат к тем же классам кодов, что и коды, исправляющие ошибки. Фактически, любой код, исправляющий ошибки, может быть также использован для обнаружения ошибок (при этом он будет способен обнаружить большее число ошибок, чем был способен исправить).

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

Блоковые коды

Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Тогда соответствующий блоковый код обычно обозначают $(n,\;k)$ . При этом число $R=\frac<k><n>» width=»» height=»» /> называется скоростью кода. Если исходные k бит код оставляет неизменными, и добавляет n − k проверочных, такой код называется систематическим, иначе несистематическим. Задать блоковый код можно по-разному, в том числе таблицей, где каждой совокупности из k информационных бит сопоставляется n бит кодового слова. Однако, хороший код должен удовлетворять, как минимум, следующим критериям: <ul> <li>способность исправлять как можно большее число ошибок,</li> <li>как можно меньшая избыточность,</li> <li>простота кодирования и декодирования.</li> </ul> Нетрудно видеть, что приведённые требования противоречат друг другу. Именно поэтому существует большое количество кодов, каждый из которых пригоден для своего круга задач. Практически все используемые коды являются линейными. Это связано с тем, что нелинейные коды значительно сложнее исследовать, и для них трудно обеспечить приемлемую лёгкость кодирования и декодирования. <h5>Линейные коды общего вида</h5> Линейный блоковый код — такой код, что множество его кодовых слов образует k -мерное линейное подпространство (назовём его C ) в n -мерном линейном пространстве, изоморфное пространству k -битных векторов. Это значит, что операция кодирования соответствует умножению исходного k -битного вектора на невырожденную матрицу G , называемую порождающей матрицей. Пусть <img decoding=$ ) можно гарантированно исправить. То есть вокруг каждого кода A имеем t -окрестность A_t , которая состоит из всех возможных вариантов передачи кода A с числом ошибок ( $1\leftrightarrow 0$ ) не более t . Никакие две окрестности двух любых кодов не пересекаются друг с другом, так как расстояние между кодами (то есть центрами этих окрестностей) всегда больше двух их радиусов $d_H(A,\;B)\geqslant d_\min&gt;2t$ .

Таким образом получив искажённый код из A_t декодер принимает решение, что был исходный код A , исправляя тем самым не более t ошибок.

Поясним на примере. Предположим, что есть два кодовых слова A и B , расстояние Хемминга между ними равно 3. Если было передано слово A , и канал внёс ошибку в одном бите, она может быть исправлена, так как даже в этом случае принятое слово ближе к кодовому слову A , чем к любому другому, и в частности к B . Но если каналом были внесены ошибки в двух битах (в которых A отличалось от B ) то результат ошибочной передачи A окажется ближе к B , чем A , и декодер примет решение что передавалось слово B .

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

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. Код Хемминга может быть представлен в таком виде, что синдром

$\overrightarrow<s>=\overrightarrow<r>H^T» width=»» height=»» />, где <img decoding=$

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора $\overrightarrow<r>_i» width=»» height=»» /> вычисляется синдром <img decoding=$

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть могут принимать значения 0 или 1.

Порождающий (генераторный) полином

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному g(x) . Порождающий полином является делителем x n − 1 .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

несистематическое кодирование осуществляется путём умножения кодируемого вектора на g(x) : v(x) = u(x)g(x) ;
систематическое кодирование осуществляется путём «дописывания» к кодируемому слову остатка от деления xn − ku(x) на g(x) , то есть $v(x)=x^<n-k>u(x)+[x^<n-k>u(x)\,\bmod\,g(x)]» width=»» height=»» />.</li> </ul> <h6>Коды CRC</h6> Коды CRC (cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления x n − k u(x) на g(x) . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же. Таким образом, вид полинома g(x) задаёт конкретный код CRC. Примеры наиболее популярных полиномов: <table border=border> <tr> <th>название кода</th> <th>степень</th> <th>полином</th> </tr> <tr> <td style=$ CRC-12 12 x 12 + x 11 + x 3 + x 2 + x + 1 CRC-16 16 x 16 + x 15 + x 2 + 1 CRC-x 16 + x 12 + x 5 + 1 CRC-32 32 x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1
Коды БЧХ

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

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

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

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

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

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

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

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

$k=7,\;R=1/2$

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

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

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

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

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

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

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

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

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

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

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

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

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

Граница Хемминга и совершенные коды

Пусть имеется двоичный блоковый (n,k) код с корректирующей способностью t . Тогда справедливо неравенство (называемое границей Хемминга):

$\sum_<i=0>^t <n\choose i>\leqslant 2^<n-k>.» width=»» height=»» /> Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида — Соломона) не являются совершенными. <h5>Энергетический выигрыш</h5> При передаче информации по каналу связи вероятность ошибки зависит от отношения сигнал/шум на входе демодулятора, таким образом при постоянном уровне шума решающее значение имеет мощность передатчика. В системах спутниковой и мобильной, а также других типов связи остро стоит вопрос экономии энергии. Кроме того, в определённых системах связи (например, телефонной) неограниченно повышать мощность сигнала не дают технические ограничения. Поскольку помехоустойчивое кодирование позволяет исправлять ошибки, при его применении мощность передатчика можно снизить, оставляя скорость передачи информации неизменной. Энергетический выигрыш определяется как разница отношений с/ш при наличии и отсутствии кодирования.<div class='code-block code-block-7' style='margin: 8px 0; clear: both;'>  <script src=$

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

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

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

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

Автоматический запрос повторной передачи

Системы с автоматическим запросом повторной передачи (ARQ — Automatic Repeat reQuest) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Запрос ARQ с остановками (stop-and-wait ARQ)

Идея этого метода заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

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

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

При этом подходе осуществляется передача только ошибочно принятых блоков данных.

См. также

Литература

Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. — ISBN 5-94836-035-0

Ссылки

Проверено 25 декабря 2006.

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Избыточное кодирование» в других словарях:

Теорема Шеннона — Хартли в теории информации применение теоремы кодирования канала с шумом к архетипичному случаю непрерывного временного аналогового канала коммуникаций, искажённого гауссовским шумом. Теорема устанавливает шенноновскую ёмкость канала,… … Википедия

Теорема Шеннона-Хартли — в теории информации применение теоремы кодирования канала с шумом к архетипичному случаю непрерывного временного аналогового канала коммуникаций, искаженного гауссовским шумом. Теорема устанавливает шенноновскую ёмкость канала, верхнюю границу… … Википедия

dvdisaster — dvdisaster … Википедия

1: — Терминология 1: : dw Номер дня недели. «1» соответствует понедельнику Определения термина из разных документов: dw DUT Разность между московским и всемирным координированным временем, выраженная целым количеством часов Определения термина из… … Словарь-справочник терминов нормативно-технической документации

DSD — Сравнение с Импульсно кодовой модуляцией (PCM). DSD (англ. Direct Stream Digital) однобитный аудиоформат, разра … Википедия

Вейвлетное сжатие — Вейвлетное сжатие общее название класса методов кодирования изображений, использующих двумерное вейвлет разложение кодируемого изображения или его частей. Обычно подразумевается сжатие с потерей качества. Существенную роль в алгоритмах… … Википедия

зона — 3.11 зона: Пространство, содержащее логически сгруппированные элементы данных в МСП. Примечание Для МСП определяются семь зон. Источник: ГОСТ Р 52535.1 2006: Карты идентификационные. Машиносчитываемые дорожные документы. Часть 1. Машин … Словарь-справочник терминов нормативно-технической документации

минимальное — 78 минимальное [максимальное] напряжение анодов сканирования (газоразрядного знакосинтезирующего индикатора); Uа.скан min [Ua.скан max]: Наименьшее [наибольшее] значение напряжения питания анодов сканирования газоразрядного знакосинтезирующего… … Словарь-справочник терминов нормативно-технической документации

Логическое кодирование

Логическое кодирование употребляется для совершенствования потенциальных кодов на подобии:

Потенциальный код с инверсией при единице NRZI;
Метод биполярного кодирования с альтернативной инверсией AMI;
Потенциальный код 2B1Q.

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

Для логического кодирования разработаны два основных способа уменьшения длинных последовательностей одинаковых бит:

избыточные коды;
скремблирование.

Избыточные коды

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

В свою очередь логический код 4В/5В, применяющийся в технологиях локальных сетей: FDDI и FastEthernet, заменяет подряд идущие 4 бита исходной последовательности на 5 бит. Из-за чего размер передаваемых данных увеличивается. В результате, вместо 16 битовых комбинаций, получаем 32 битовых комбинации, в которых можно выбрать такие комбинации бит, которые будут содержать наименьшее количество подрят идущих одиннаковых последовательностей бит. А оставшиеся 16 комбинаций пометить как запрещенные, что придает избыточному коду свойство распозновать искаженные биты. Если поступила запрещенная комбинация — сигнал исказился.

Таблица — Соответствие исходных и результирующих кодов 4В/5В

Код 4В/5В затем передается по линии с помощью физического кодирования по одному из методов потенциального кодирования, чувствительному только к длинным последовательностям нулей. Символы кода 4В/5В длиной 5 бит гарантируют, что при любом их сочетании на линии не могут встретиться более трех нулей подряд.

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

Скремблирование

Скремблирование (англ. scramble — перемешивать) — разновидность кодирования информации, для передачи по каналам связи и хранения, улучшаюшая спектральные и статиcтические характеристики.

Скремблирование есть приведение информации к виду, по различным характеристикам похожему на случайные данные.

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

Методы скремблирования заключаются в побитном вычислении результирующего кода на основании бит исходного кода и полученных в предыдущих тактах бит результирующего кода. Например, скремблер может реализовывать следующее соотношение:

где Вi, — двоичная цифра результирующего кода, полученная на i-м такте работы скремблера, Ai — двоичная цифра исходного кода, поступающая на вход скремблера, Вi-3 и Bi-5 — двоичные цифры результирующего кода, полученные на предыдущих тактах работы скремблера, соответственно на 3 и на 5 тактов ранее текущего такта, операция исключающего ИЛИ (сложение по модулю 2).

Например, для исходной последовательности 111000000001 скрэмблер даст следующий результирующий код:

Таким образом, на выходе скремблера появится последовательность 111110001100, в которой нет последовательности из восьми нулей, присутствовавшей в исходном коде.

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

Произведем обратную операцию с последовательностью 111110001100, для получения исходной последовательности:

Получаем исходную последовательность: 111000000001.

Различные алгоритмы скремблирования отличаются количеством слагаемых, дающих цифру результирующего кода, и сдвигом между слагаемыми. Так, в сетях ISDN при передаче данных от сети к абоненту используется преобразование со сдвигами в 5 и 23 позиции, а при передаче данных от абонента в сеть — со сдвигами 18 и 23 позиции.

Для улучшения кода AMI используются два метода, основанные на искусственном искажении последовательности нулей запрещенными символами:

метод B8ZS (Bipolarwith 8-ZerosSub¬stitution) — исправляет только последовательности, состоящие из 8 нулей. Для этого он после первых трех нулей вместо оставшихся пяти нулей вставляет пять цифр: V-l*-0-V-l*. V здесь обозначает сигнал единицы, запрещенной для данного такта полярности, то есть сигнал, не изменяющий полярность предыдущей единицы, 1* — сигнал единицы корректной полярности, а знак звездочки отмечает тот факт, что в исходном коде в этом такте была не единица, а ноль.

метода HDB3 (High-DensityBipolar 3-Zeros) — исправляет любые четыре подряд идущих нуля в исходной последовательности. Каждые четыре нуля заменяются четырьмя сигналами, в которых имеется один сигнал V. Для подавления постоянной составляющей полярность сигнала V чередуется при последовательных заменах. Кроме того, для замены используются два образца четырехтактовых кодов. Если перед заменой исходный код содержал не¬четное число единиц, то используется последовательность 000V, а если число единиц было четным — последовательность l*00V.

V — сигнал единицы запрещенной полярности;

1* — сигнал единицы корректной полярности, но заменившей 0 в исходном коде

Электронные средства сбора, обработки и отображения информации

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

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

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

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

Блоковый код называется равномерным, если п (значность) остается одинаковой для всех букв сообщения.

Различают разделимые и неразделимые блоковые коды.

При кодировании разделимыми кодами кодовые операции состоят из двух разделяющихся частей: информационной и проверочной. Информационные и проверочные разряды во всех кодовых комбинациях разделимого кода занимают одни и те же позиции.

При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно.

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

Общие принципы использования избыточности

Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных символов. На ввод кодирующего устройства поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из п двоичных символов, причем n>k. Всего может быть различных входных последовательностей и различных выходных последовательностей. Из общего числа выходных последовательностей только последовательностей соответствуют входным. Будем называть их разрешенными кодовыми комбинациями. Остальные ( — ) возможных выходных последовательностей для передачи не используются. Их будем называть запрещенными кодовыми комбинациями.

Искажение информации в процессе передачи сводится к тому, что некоторые из передаточных символов заменяются другими — неверными. Каждая из разрешенных комбинаций в результате действия помех может трансформироваться в любую другую. Всего может быть · возможных случаев. В это число входит:

— случаев безошибочной передачи;

— ·(-1) случаев перевода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам;

— ·( — ) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены.

Часть обнаруживаемых ошибочных кодовых комбинаций от общего числа возможных случаев передачи соответствует:

Рассмотрим, например, обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (п=k+1). Общее число выходных последовательностей составит , то есть вдвое больше общего числа кодируемых входных последовательностей. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество комбинаций, содержащих четное число единиц (или нулей). При кодировании к каждой последовательности из k информационных символов добавляется один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Искажение любого четного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть обнаруженных ошибок составляет:

Пример кодирующего устройства с проверкой на четность показан на рис.

Основные параметры корректирующих кодов

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

Рассмотрим суть этих параметров.

Избыточность корректирующего кода может быть абсолютной и относительной. Под абсолютной избыточностью понимают число вводимых дополнительных разрядов

Относительной избыточностью корректирующего кода называют величину

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

Если производительность источника равна Н символов в секунду, то скорость передачи после кодирования этой информации будет равна

поскольку в последовательности из п символов только k информационных.

Рис. 2.5 — Кодер с контролем на четность

Если число ошибок, которое нужно обнаружить или исправить, значительно, необходимо иметь код с большим числом проверочных символов. Скорость передачи информации при этом будет уменьшена, так как появляется временная задержка информации. Она тем больше, чем сложнее кодирование.

Кодовое расстояние характеризует cтепень различия любых двух кодовых комбинаций. Оно выражается числом символов, которыми комбинации отличаются одна от другой.

Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2.

Кодовое расстояние может быть различным. Так, в первичном натуральном безызбыточном коде это расстояние для различных комбинаций может различаться от единицы до п, равной значности кода.

Число обнаруживаемых ошибок определяется минимальным расстоянием между кодовыми комбинациями. Это расстояние называется хэмминговым.

В безызбыточном коде все комбинации являются разрешенными, =1. Достаточно только исказиться одному символу, и будет ошибка в сообщении.

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

Доказательство. Возьмем значность кода п=3. Возможные комбинации натурального кода образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111. Любая одиночная ошибка трансформирует данную комбинацию в другую разрешенную комбинацию. Ошибки здесь не обнаруживаются и не исправляются, так как =1. Если =2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию.

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

000, 011, 101, 110 — разрешенные комбинации;

001, 010, 100, 111 — запрещенные комбинации.

Очевидно, что искажение помехой одного разряда (одиночная ошибка) приводит к переходу комбинации в подмножество запрещенных комбинаций. То есть этот код обнаруживает все одиночные ошибки.

В общем случае при необходимости обнаруживать ошибки кратности — минимальное хэммингово расстояние должно быть, по крайней мере, на единицу больше , то есть

В этом случае никакая ошибка кратности не в состоянии перевести одну разрешенную комбинацию в другую.

Ошибки можно не только обнаруживать, но и исправлять.

Теорема. Для исправления одиночной ошибки каждой разрешенной кодовой комбинации необходимо сопоставить подмножество запрещенных кодовых комбинаций. Чтобы эти подмножества не пересекались, хэммингово расстояние должно быть не менее трех.

Доказательство. Пусть, как и в предыдущем примере, п=3. Примем разрешенные комбинации 000 и 111 (кодовое расстояние между ними равно 3). Разрешенной комбинации 000 поставим в соответствие подмножество запрещенных комбинаций 001, 010, 100. Эти запрещенные комбинации образуются в результате возникновения единичной ошибки в комбинации 000.

Аналогично разрешенной комбинации 111 необходимо поставить в соответствие подмножество запрещенных комбинаций 110, 011, 101. Если сопоставить эти подмножества запрещенных комбинаций, то очевидно, что они не пересекаются:

В общем случае исправляемые ошибки кратности связаны с кодовым расстоянием соотношением

Для ориентировочного определения необходимой избыточности кода при заданном кодовом расстоянии d можно воспользоваться верхней граничной оценкой для r = n — k, называемой оценкой Хэмминга:

где — сочетание из п элементов по t (число возможных ошибок кратности t на длине п-разрядной комбинации).

Если, например, п=7, =1, то из (2.1)

=3, n — k (1+7)=3 .

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

Групповой код с проверкой на четность

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

Строки образуются последовательно по мере поступления символов исходного кода. Затем после формирования т строк матрицы производится проверка на четность ее столбцов и образуются контрольные символы . Контрольные символы образуются путем суммирования по модулю 2 информационных символов, расположенных в столбце:

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

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

Если проверка проводится по строкам и столбцам, то код называется матричным.

Проверочные символы располагаются следующим образом:

В этом случае не обнаруживаются только ошибки четной кратности с кратностью 4, 8, 16 и т.д., при которых происходит искажение символов с попарно одинаковыми индексами строк столбцов. Наименьшая избыточность кода получается в том случае, когда образуемая матрица является квадратной.

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

Матричный код позволяет исправлять одиночные ошибки. Ошибочный элемент находится на пересечении строки и столбца, в которых имеется нарушение четности.

Коды с постоянным весом

Весом называется число единиц, содержащихся в кодовых комбинациях.

Если число единиц во всех комбинациях кода будет постоянным, то такой код будет кодом с постоянным весом. Коды с постоянным весом относятся к классу блочных неразделимых кодов, поскольку здесь невозможно выделить информационные и проверочные символы. Наибольшее применение получили коды «3 из 7», «3 из 8», хотя возможны другие варианты. Первая цифра указывает на вес кода, вторая — на общее число символов в комбинации.

Разрешенными комбинациями кода «3 из 7» являются такие, которые содержат три единицы независимо от их места в комбинации, например 1110000 или 1010100 и т.д. Обнаружение ошибок сводится к определению их веса. Если вес отличается от заданного, то считается, что произошла ошибка. Код обнаруживает веса ошибок нечетной кратности и части ошибок четной кратности. Не обнаруживаются ошибки, при которых несколько единиц превращается в нули и столько же нулей — в единицы (ошибки смещения), так как при этом вес кода не изменяется.

В коде «3 из 7» возможных комбинаций сто двадцать восемь (=128), а разрешенных кода только тридцать пять. Относительная избыточность _отн = 0,28.

Схема устройства определения веса комбинаций кода «3 из 7» приведена на рис. 2.6.

Рис. 2.6 — Схема определения веса комбинаций кода «3 из 7»

Циклические коды

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

— комбинация циклического кода;

— также комбинация циклического кода.

При рассмотрении циклических кодов двоичные числа представляют в виде многочлена, степень которого (п — 1), п — длина кодовой комбинации.

Например, комбинация 1001111 (п=7) будет представлена многочленом

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

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

Построение комбинаций циклического кода возможно путем умножения исходной комбинации А(х) на образующий полином G(x) с приведением подобных членов по модулю 2:

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

Таким образом, все полиномы, отображающие комбинации циклического кода, будут иметь степень ниже п.

Часто в качестве полинома, на который осуществляется деление, берется полином G(x)=+1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.

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

Число разрядов регистра выбирается равным степени образующего полинома.

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

На рис. 2.7 приведена схема кодирующего регистра для преобразования четырехразрядной комбинации в семиразрядную.

Рис. 2.7 — Схема кодирующего регистра

В табл. 2.3 показано, как путем сдвигов исходной комбинации 0101 получается комбинация циклического кода 1010011. п=7, k=4. Комбинация 0101, ключ в положении 1. В течение первых четырех тактов регистр будет заполнен, затем ключ переводится в положение 2. Обратная связь замыкается. Под действием семи сдвигающих тактов проходит формирование семиразрядного циклического кода.

Свойства циклического кода:

1) циклический код обнаруживает все одиночные ошибки, если образующий полином содержит более одного члена. Если G(x)=x+1, то код обнаруживает одиночные ошибки и все нечетные;

2) циклический код с G(x)=(x+1)G(x) обнаруживает все одиночные, двойные и тройные ошибки;

3) циклический код с образующим полиномом G(x) степени r = n — k обнаруживает все групповые ошибки длительностью в r символов.