Методика исследования способности кода исправлять ошибки

Задайте в 'источнике ошибок' однократную ошибку (например 1000000).

Убедитесь, что на выходе 'Декодера 1' будет та же последовательность,

что и в 'Источнике'.

Сместите циклически 6 раз вектор ошибки и убедитесь, что при любой

однократной ошибке 'Декодер 1' правильно её исправит.

При выполнении этого пункта обратите внимание, что синдром ошибки зависит от вектора ошибки и не зависит от передаваемой комбинации.

По результатам этого пункта сделайте распечатку (Распечатка №2).

Методика проверки ошибочного декодирования в режиме исправления ошибок.

Задайте в 'Источнике ошибок' несколько векторов ошибок с кратностью от 2 до 7. Убедитесь, что при таких ошибках последовательность на выходе 'Декодера 1' не будет совпадать с последовательностью, которую Вы задали в 'Источнике'.

По результатам этого пункта сделайте распечатку (Распечатка №3).

Методика исследования способности кода обнаруживать ошибки

Задайте в 'Источнике ошибок' различные ошибки кратностью от 1 до 7.

Убедитесь, что подавляющее большинство векторов ошибок будет обнаружено (на панели 'Декодер 2' будет гореть индикатор 'Обнаружена ошибка').

По результатам этого пункта сделайте распечатку (Распечатка №4).

Методика проверки факта не обнаружения ошибки кодом

Задайте в 'Источнике ошибок' различные ошибки кратностью от 3 до 7.

Убедитесь, что имеются вектора ошибок, которые кодом не обнаруживаются (при наличии ошибки на панели 'Декодер 2' не будет гореть индикатор 'Обнаружена ошибка').

По результатам этого пункта сделайте распечатку (Распечатка №5).

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

Перейдите на закладку 'таблицы' и нажмите клавишу 'Печать'

Содержание отчета

Отчёт должен содержать:

стр 1. Титульный лист.

стр 2. Цель работы и функциональную схему лабораторного макета.

!!! Функциональную схему нарисуйте использую карандаш и линейку.

стр 3. Индивидуальное задание.

стр 4. Распечатку №1, показывающую работу кодера и правильности декодирования при отсутствии ошибок.

Распечатку №2, показывающую способности кода исправлять однократную ошибку.

стр 5. Распечатку №3, показывающую факт ошибочного декодирования в режиме исправления ошибок. Распечатку №4, показывающую способности кода обнаруживать ошибки.

стр 6. Распечатку №5, показывающую факт не обнаружения ошибки кодом.

Распечатку №6, показывающую разрешенные кодовые комбинации и

расстояния Хемминга.

стр 7. Краткий ответ на 5 контрольных вопросов (номера вопросов выберите самостоятельно) и выводы по работе.

*** Образец оформления отчёта смотрите в файле: ЛР_13_Образец_отчёта.doc

Список литературы

1. Шварцман В.0., Емельянов Г.А. Теория передачи дискретной информации. - М.: Связь, 1979. - 424 с.

2. Шварцман В.0., Емельянов Г.А. Передача дискретной информации. - М.: Радио и связь, 1982. - 239 с.

3. Передача дискретных сообщений. Под редакцией В.П.Шувалова.

[с. 49 - 54; с. 245 - 297] –М.: Радио и связь, -1990-464 c.: ил.-

8. Контрольные вопросы

1. Поясните понятия: блочные, непрерывные, разделимые, неразделимые, итеративные, линейные, циклические коды?

2. Что такое расстояние Хемминга и кодовое расстояние?

3. Определение и основные свойства циклического кода.

4. Какое правило кодирования циклическим кодом принято в лабораторной работе?

5. Какое правило декодирования принято в декодере в режиме исправления ошибок?

6. Какое правило декодирования принято в декодере в режима обнаружения ошибок?

7. Как связаны кратности гарантированно исправляемых кодом ошибок t и гарантированно обнаруживаемых кодом ошибок s с кодовым расстоянием d?

8. Какие векторы ошибок не могут быть обнаружены линейным циклическим кодом?

9. Сколько различных векторов ошибок может быть исправлено, не исправлено, обнаружено, не обнаружено кодом (7, 4).?

10. Как рассчитать вероятность не обнаружения ошибки при заданном канале?

11. Как рассчитать вероятность ошибочного декодирования при заданном канале?

12. Как по одной известной разрешённой комбинации циклического кода определить все остальные кодовые комбинации этого кода?

13. Известна комбинация на входе кодера v1 и выходе декодера_2 v2.

Как определить вектор ошибки E? ( v1< > v2 )

14. Дана длина кодовой комбинации n, вероятность ошибки в канале Pош.

Как определить вероятность появления в кодовой комбинации ошибки

кратностью t?

15. Как производится кодирование - декодирование при использовании кода с проверкой на чётность (на нечётность)?

ПРИЛОЖЕНИЕ

КРАТКИЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ЛИНЕЙНЫХ ЦИКЛИЧЕСКИХ КОДОВ

 

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

Линейным кодом называют блочный (n, k) код, символы кодовых слов которого являются линейными комбинациями информационных символов.

Если M=(m_k-1, m_k-2, ….m₀) обозначает последовательность k двоичных информационных символов, то правило образования кодового слова V разделимого линейного кода с длиной блока n > k из последовательности M можно записать системой линейных уравнений:

(I)

где - знак суммирования по модулю 2, коэффициенты d_{l, i} являются символами двоичного алфавита, они могут быть выбраны произвольно, но должны быть фиксированными для данного кода.

Приведем ряд свойств линейных кодов [1, c.283-286].

1. Сумма по модулю 2 двух кодовых слов также является кодовым словом (свойство замкнутости по отношению к операции сложения).

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

Расстояние Хемминга между двумя кодовыми словами равно числу единиц в сумме этих слов по модулю 2, т.е. количеству разрядов, в которых различаются эти два кодовых слова. Например:

первое кодовое слово: 1000110,

второе кодовое слово: 0100010,

сумма по модулю два: 1100100 -> расстояние Хемминга равно 3.

 

Кодовое расстояние d, связано с кратностью t гарантированно исправляемых кодом ошибок соотношением

и с кратностью гарантированно обнаруживаемых кодом ошибок соотношением

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

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

Циклическим сдвигом называется операция, превращающая вектор V₁= (v₁ , v₂ , v₃, …v_n) в вектор V₂= (v_n, v₁, v₂ , …v_n-1) –сдвиг в право, или в вектор V3 = (v₂ , v₃, …v_n, v₁) – сдвиг влево.

Например, дан вектор 0001011. При циклическом сдвиге

вправо получится вектор 1000101.

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

Установим формальное соответствие между кодовыми словами и степенными полиномами. Кодовому слову

V= (v_n-1, v_n-2 , v_n-3 , …v₁ , v₀)

где v_n-1, v_n-2 , v_n-3 , …v₁ , v₀ двоичные числа, можно поставить в соответствие полином (n-1)-й степени

V(x) = v_n-1 x^n-1 + v_n-2 x^n-1 + …+ v₁ x + v₀.

Такая запись соответствует записи числа в виде многочлена в двоичной системе счисления, где x - основание системы счисле­ния.

Например, кодовому слову 0001011 соответствует полином

x³ + x + 1, кодовому слову 0100110 – полином x⁵ + x² +x.

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

( ) ( ) = ( ).

Этому полиному соответствует слово 0101101, т.е. результат поразрядного сложения по модулю 2 слов 0001011 и 0100110.

Умножение полинома v(x)на x по модулю (xⁿ Å 1) соответствует циклическому сдвигу кодового слова влево на один разряд.

Числом А по модулю В называется остаток от деления А на В и обозначается A mod B.

В вашем случае все полиномы степени выше (n-1) заменяются остатком отих деления на полином xⁿ Å 1.

Среди всех полиномов, соответствующих кодовым словам циклического кода, имеется ненулевой полином g(x) наименьшей степени. Этот полином полностью определяет соответствующий код и поэтому называется образующим [l, с. 297-293].

Степень образующего полинома g(x) равна n-k, свободный член всегда равен единице.

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

Нулевая комбинация обязательно принадлежит любому линейному циклическому коду и может быть записана как (xⁿ Å 1) mod (xⁿ Å 1) = 0. Следовательно, образующий полином g(x) должен быть делителем бинома xⁿ Å 1.

Это даёт конструктивную возможности построения циклического кода заданной длины n: любой полином, являющийся делителем бинома xⁿ Å 1, можно использовать в качестве образующего.

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

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

Для построения разделимого циклического кода используется следующее правило построения кодовых слов [1, с. 300] [2, с. 110-113]

V(x) = m(x)*x^n-k Å r(x),

где r(x) - остаток от деления m(x)*x^n-k на g(x).

Степень r(x), очевидно, меньше (n-k), а потому в кодовом слове первые k, символов будут совпадать с информационными, а последние n - k символов будут проверочными.

Получить все разрешённые комбинации циклического кода можно по одной известной кодовой комбинации (не нулевой). Для этого сначала надо циклически сдвинуть известную комбинацию k-1 раз. В результате получится n комбинаций. Затем сложить попарно по модулю 2 получившиеся комбинации в различных сочитаниях (по две, по три и.т.д). Нулевую комбинацию (все нули) можно получить, сложив по модулю 2 любую комбинацию саму с собой. Всего получится 2^k кодовых слов.

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

В режиме обнаружения ошибок, если принятая последовательность делится без остатка на g(x), делается вывод, что ошибки нет или она не обнаруживается. В противном случае комбинация бракуется.

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

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

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

Относительно просто эти вероятности могут быть рассчитаны для двоичного симметричного канала (ДСК) без памяти.

В таком канале каждый двоичный символ с некоторой фиксированной вероятностью (1 - p₀) принимается правильно и с вероятностью p₀ изменяется помехой на обратный. Передача - приём каждого символа полагается событием независимым (канал без памяти).

Если по такому каналу передается кодовое слово длины n, то вероятность P_n(0) того, что не произойдет ни одной ошибки, равна (1- p₀)ⁿ.

Вероятность P_n(1) того, что будет одна ошибка в заданном символе, равна p₀*(1- p₀)^n-1.

Вероятность того, что слово на выходе канала будет отличаться от переданного слова в заданных t разрядах, т.е. вектор, ошибок содержит t единиц, равна P^*=p₀^t (1 - p₀) ^n-t.

t

t

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

P_n (t) = C_n p₀^t (1 - p₀) ^n-t., где С_n – число сочетаний из n по t.

Число единиц в векторе ошибок часто называют его весом.

Положим некоторый линейный код (5, 3) содержит одно нулевое слово (как всякий линейный код), два слова веса 2, четыре слова веса 3, одно слово веса 4 (всего слов).

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

В режиме исправления ошибок декодер вычисляет остаток S(x) от деления принятой последовательности P(x) на g(x). Этот остаток называют синдромом. Принятый полином P(x) представляет собой сумму по модулю два переданного слова V(x) и вектора ошибок E(x):

P(x) = V(x) Å E(x)

Тогда синдром S(x)= P(x) mod g(x), так как по определению циклического кода V(x)mod g(x) =0.

Оопределенному синдрому S(x) может быть поставлен в соответствие определенный вектор ошибок E(x). Тогда переданное слово V(x) находят, складывая P(x)Å E(x).

Однако один и тот же синдром может соответствовать 2^k различным векторам ошибок. Положим, синдром S(x) соответствует вектору ошибок E₁(x). Но и все векторы ошибок, равные сумме E₁(x) Å V(x), где V(x) любое кодовое слово, будут давать тот же синдром. Поэтому, поставив в соответствие синдрому S1(x) вектор ошибок E₁(x), мы будем осуществлять правильное декодирование в случае, когда действительно вектор ошибок равен E₁(x), во всех остальных 2^k-1 случаях декодирование будет ошибочным.

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

Например, в ДСК, в котором вероятность p₀ ошибочного приёма двоичного символа много меньше вероятности (1 - p₀) правильного приема, вероятность появления векторов ошибок уменьшается с увеличением их веса t. В этом случае следует исправлять в первую очередь вектор ошибок меньшего веса.

Если кодом могут быть исправлены только все векторы ошибок веса t и меньше, то любой вектор ошибки веса от t + 1до n, будет приводить к ошибочному декодированию.

Вероятность ошибочного декодирования будет равна вероятности P_n(> t) появления векторов ошибок веса t + 1 и больше в заданном канале. Для ДСКэта вероятность будет равна

i i

.

Общее число различных векторов ошибок, которые может исправлять циклический код, равно числу ненулевых синдромов – 2^n-k - 1.

 

⇐ Предыдущая12

Поделиться:

Популярное:

1. I. Объект и средства исследования
2. II. Практические исследования
3. II. Специальные исследования
4. IX. ДАННЫЕ ЛАБОРАТОРНЫХ, ИНСТРУМЕНТАЛЬНЫХ МЕТОДОВ ИССЛЕДОВАНИЯ И КОНСУЛЬТАЦИИ СПЕЦИАЛИСТОВ
5. Анализ результатов экспериментального исследования по реализации программы педагогического сопровождения молодой семьи
6. АНАЛИТИЧЕСКИЕ НАУЧНЫЕ ИССЛЕДОВАНИЯ НА АВТОМОБИЛЬНОМ ТРАНСПОРТЕ
7. АППАРАТУРА И МЕТОДЫ ИССЛЕДОВАНИЯ
8. Биология – теоретическая основа медицины. Методы исследования и этапы развития биологии.
9. Биопсийный материал для гистологического исследования
10. Введение. Электрофизиологические исследования сердца
11. ВЗЯТИЕ КАЛА ДЛЯ ЛАБОРАТОРНОГО ИССЛЕДОВАНИЯ
12. Взятие мокроты для бактериологического исследования (на чувствительность к антибиотикам)