vopros-otvet (519806), страница 19

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

Текст из файла (страница 19)

0010101001011.

Последовательность в контрольной точке К₇:

0001011110000.

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

Рассмотрим подробнее последовательность в точке К₇. Будем считать, что произошел наихудший случай – исказилось b символов. Следовательно, будет поражено b/2 информационных и b/2 проверочных символов. До поступления первого ошибочного символа на входе регистр содержит безошибочные информационные символы. Поэтому в течение первых b/2 тактов в синдроме возникают единицы за счет ошибок в проверочных символах. На этом пачка ошибок заканчивается, и в дальнейшем на выходной сумматор формирователя синдрома будут поступать лишь безошибочные проверочные символы. За следующие b тактов единицы формируются в синдроме с начала за счет поступлений ошибочных информационных символов из первого полурегистра, а за тем – из второго. Итак последовательность в точке К₇ (синдром) содержит:

1. Единицы на местах ошибок в проверочных символах.

2. Со сдвигом на b/2 от соответсвующих проверочных символов единицы на местах ошибок в информационных символах.

000100000000…

__0001100000…

____00011000…

Теперь видно, что произошла ошибка в 4-м проверочном и 4-м и 5-ом информационных символах (соответственно в 7-м, 8-м и 9-м символах общей последовательности). Вторая часть схемы (узел коррекции) позволяет провести исправление ошибок в информационных символах автоматически. Анализатор синдрома построен в точном соответствии с его структурой. На выходе схемы “НЕ” получим инвертированную последовательность, т.е. последовательность:

1110100001111.

На втором входе схемы “И” получаем последовательность, сдвинутую на два такта относительно последовательности в точке К₇:

0000010111100.

На третьем входе схемы “И” получаем последовательность, сдвинутую относительно последовательности в точке К₇ на четыре такта, т.е.:

0000000101111.

На выходе схемы “И” (на три входа) получаем последовательность (см. контрольную точку К₈), которая должна исправить нашу последовательность информационных сигналов.

1110100001111

0000010111100

0000000101111

0000000001100 – последовательность в точке К₈.

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

Последовательность в точке К₆:

0000100010111001.

Последовательность в точке К₈:

00000110000000.

Исправленная последовательность на выходе (см. контрольную точку К₉):

100100111001.

На пути информационных символов в декодирующем устройстве имеется всего 3b/2 ячеек. Это соответствует 3b символам во входной последовательности. Отсюда, чтобы вывести все ошибочные символы из схемы требуется промежуток из 3b + 1 безошибочных символов. Чтобы не проводить исправление в случае появления ошибочных символов в этот период и предусмотрена схема “НЕ”.

Аналогичным образом строятся схемы кодирующего и декодирующего устройств для исправления пачки ошибок длиной не более b = 2; 6; 8; 10; 12 и т.д.

43.Итеративные коды. Код с повторениями.

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

В связи с этим итеративные коды (ИК) так же называются многомерными, многосоставными.

Число информационных символов в кодовом блоке q-степенного кода равно:

,

где K_γ – число информационных символов по координате γ.

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

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

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

Рис. 8.1

Значения проверочных символов, располагающихся в крайнем правом (или в любом другом) столбце и нижней строке, определяются уравнениями:

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

Исправление при тройной ошибке соответствует внесению новой ошибки, вместо исправления старой (ложное исправление, рис. 8.2, г).

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

Рис. 8.2

Число ошибок такого вида В4 для блока из l · n символов равно:

Общее число четырехкратных ошибок составляет:

.

Таким образом, отношение

.

При n = 8; l = 250 имеем:

.

Аналогичный расчет для шестикратных ошибок (рис. 8.3) типа

.

Рис. 8.3

Минимальное кодовое расстояние итеративного кода равно:

,

где D_γ – кодовое расстояние линейного кода по координате γ.

Коррекция ошибок проводится последовательно. Сначала исправляют ошибки по одной координате, затем осуществляют исправление оставшихся ошибок по другой координате и т.д. Такая процедура проста, но снижает корректирующую способность итеративного кода, поскольку оказывается невозможным исправить часть ошибок кратности (d – 1)/2.

Имеем два кода Хэмминга (7; 4).

Результирующий итеративный код (49; 16) имеет минимальное кодовое расстояние, равное 3 · 3 = 9, и, следовательно, потенциально, как любой линейный код, способен исправлять все ошибки кратности 4 и менее. Однако, применяя указанную выше процедуру декодирования, невозможно исправить четырехкратные ошибки с расположением искаженных символов в вершинах прямоугольника.

Код с повторениями:

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

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

При одноразовом повторении К.К. ошибка повторяется в одном и том же разряде с вероятностью

.

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

,

второй ошибки:

и т.д.

.

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

Модифицированный код с повторением

1. Значения проверочных разрядов повторяют информационные, если число единиц в информационных разрядах четно.

2. Значения проверочных разрядов инвертируются, если число единиц в информационных разрядах нечетно.

Это код с однократным повторением и инверсией (2k, k).

Пример 1

Имеем кодовую комбинацию:

1001 1001,

где

• первые 4 разряда – информационные;

• вторые 4 разряда – проверочные.

Так как число единиц в информационных разрядах четно, то значение проверочных разрядов повторяют информационные.

Получили из линии связи кодовую комбинацию:

1101 1101.

Проверяем, количество единиц в информационных разрядах – нечетно, должна быть – инверсия:

1101 0010.

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

Пример 2

Имеем кодовую комбинацию:

1011 0100.

Получили из линии связи кодовую комбинацию:

1111 0000.

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

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

суммирование проводится только по четным i.

Характеристики

Список файлов ответов (шпаргалок)