Различие между итеративным и каскадным кодом

Различие между итеративным и каскадным кодом

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

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

К этим символам приписываются еще (N2 — k2) проверочных символов m-го кода также в виде строк длиной N1. К каждой из этих строк приписываются двоичные проверочные символы в соответствии с внутренним кодом N1,k1.

В процессе приема сначала декодируются (с обнаружением или исправлением ошибок) все блоки внутреннего кода, а затем декодируется блок внешнего m-го кода (N2,k2), причем исправляются ошибки, оставшиеся после декодирования внутреннего кода. В качестве внешнего кода используют обычно m-й код Рида —Соломона, обеспечивающий наибольшее возможное значение d при заданных N2 и k2 если N2<m.

Процедура мажоритарного декодирования

Процедура мажоритарного декодирования

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

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

Мощные коды (т.е. коды с длинными блоками и большим кодовым расстоянием d) можно строить, объединяя несколько коротких кодов. Так строится, например, итеративный код из двух линейных систематических кодов (N1 k1,) и (N2,k2). Вначале сообщение кодируется кодом первой ступени (N1,k2). Кодированная последовательность разбивается на блоки по к2 символов. Эти символы считаются информационными для кода второй ступени. При кодировании на второй ступени к каждому блоку из информационных символов приписываются (N2 — k2) проверочных. В результате получается блок, содержащий N1N2 символов, из которых k1,k2 являются информационными.

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

Минимальное кодовое расстояние для двухмерного итеративного кода равно произведению минимальных кодовых расстояний для кодов первой и второй ступеней, т.е. d= d1 d2.

Режим с восстановлением стертых ненадежных символов

Режим с восстановлением стертых ненадежных символов

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

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

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

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

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

Непрерывные коды не разбиваются на блоки

Непрерывные коды не разбиваются на блоки

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

К числу основных характеристик кода относятся длина кода n, его основание m, мощность N (число разрешенных кодовых комбинаций), полное число кодовых комбинаций N0, число информационных символов k, число проверочных символов r = N — k, вес кодовой комбинации (число единиц в комбинации), избыточность кода и кодовое расстояние. Избыточность кода определяется выражением:

Непрерывные коды не разбиваются на блоки

Наименьшее расстояние Хемминга для данного кода называется кодовым расстоянием d.

При независимых ошибках в канале через кодовое расстояние удобно выражается корректирующая способность кода. Если код имеет d = 1, то две кодовые комбинации отличаются минимум в одном символе. Искажение одного символа сразу трансформирует кодовую комбинацию в другую разрешенную, т.е. код с d = 1 не способен корректировать ошибки. Чтобы код мог обнаруживать любую одиночную ошибку, необходимо обеспечить кодовое расстояние, равное двум. Рассуждая аналогичным образом, можно получить, что для обнаружения всех ошибок кратности l требуется код с расстоянием:

Непрерывные коды не разбиваются на блоки

Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние, нежели для их обнаружения. Если кратность исправляемых ошибок равна l, то кодовое расстояние должно удовлетворять условию:

Непрерывные коды не разбиваются на блоки

Линейные и нелинейные коды

Линейные и нелинейные коды

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

Наиболее простой линейный систематический код — это (n, n — 1), содержащий один проверочный символ, который равен сумме по модулю 2 всех информационных символов. Такой код называется кодом с проверкой на четность. Он позволяет обнаружить все сочетания ошибок нечетной кратности.

Вероятность необнаруженной ошибки в первом приближении можно определить как вероятность искажения двух символов:

Линейные и нелинейные коды

style="display:block; text-align:center;"
data-ad-format="fluid"
data-ad-layout="in-article"
data-ad-client="ca-pub-6007240224880862"
data-ad-slot="8925203109">

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

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

Например, таким является код: 00000; 00101; 01001; 01110; 10001; 11010, 11111. Коды Бергера применяются, как правило, в асимметричных каналах. В симметричных каналах они обнаруживают рее одиночные ошибки и некоторую часть многократных.

Блочные коды

Блочные коды

Блочные коды бывают разделимыми и неразделимыми. К разделимым относятся коды, в которых каждый из символов может быть отнесен к одной из двух непересекающихся групп: информационные символы, несущие сообщение, и проверочные, служащие исключительно для обнаружения и исправления ошибок. Такие коды принято обозначать парой чисел (n, k:), где n — длина кода; k — число информационных символов.

Число разрешенных комбинаций в коде (n, k) не превышает 2k неразделимым относятся коды, у которых нельзя выделить информационные и проверочные символы. Неразделимые коды — это, например, коды с постоянным весом и коды на основе матриц Адамара. Коды с постоянным весом характеризуются тем, что все их кодовые комбинации содержат одинаковое число единиц. Примером такого кода является стандартный телеграфный код, у которого в каждой кодовой комбинации по три единицы и четыре нуля (код «3 из 7»: (7,3)).

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

Блочные коды

Страница 30 из 45« Первая...1020...2829303132...40...Последняя »
Яндекс.Метрика