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

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

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

Таблица 5.8

N	a7	a6	a5	a3	a4	a2	a1
1	0	0	0	1	0	1	1
2	0	0	1	0	1	0	1
3	0	1	0	0	1	1	0
4	1	0	0	0	1	1	1
5	0	0	1	1	1	1	0
6	0	1	0	1	1	0	1
7	1	0	0	1	1	0	0
8	0	1	1	0	0	1	1
9	1	0	1	0	0	1	0
10	1	1	0	0	0	0	1
11	0	1	1	1	0	0	0
12	1	0	1	1	0	0	1
13	1	1	0	1	0	1	0
14	1	1	1	0	1	0	0
15	1	1	1	1	1	1	1

a₄, a₂, a₁ – проверочные символы; a₇, a₆, a₅, a₃ – информационные символы.

Однако, при больших значениях n и k эта запись громоздка и ее записывают в сокращенном виде. Строки полученной матрицы линейно зависимы. Строка №5 = №1 Е №2. Для полного определения кода достаточно записать только линейно независимые строки. Среди 2^k – 1 КК их только 4. Эту матрицу можно назвать образующей (порождающей, производящей по отношению к данному коду). Полное множество РКК можно получить из М(7; 4), суммируя по модулю 2 строки соответствующей матрицы во всех возможных сочетаниях.

.

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

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

Любой символ a_i, выражается d (минимальное кодовое расстояние) различными независимыми способами в виде линейных комбинаций других символов. При этом может использоваться тривиальная проверка a_i = a_i. Результаты вычислений подаются на соответствующий этому символу мажоритарный элемент. Последний представляет собой схему, имеющую d входов и один выход, на котором появляется единица, когда возбуждается больше половины его входов, и нуль, когда возбуждается число таких входов меньше половины. Если ошибки отсутствуют, то проверочные равенства не нарушаются, и на выходе мажоритарного элемента получаем истинное значение символа. Если число проверок d ^{(2s + 1)} и появление ошибки кратности s и менее не приводит к нарушению более s проверок, то правильное решение может быть принято по большинству неискаженных проверок. Чтобы указанное условие выполнялось, любой другой символ a_j ( j неравно i) не должен входить более чем в одно проверочное равенство. В этом случае мы имеем дело с системой разделенных проверок.

Для кода (8; 2) получим:

a₅ = a₆ Е a₁; a₈ = a₃ Е a₁;

a₅ = a₇ Е a₂; a₈ = a₄ Е a₂;

a₅ = a₃; a₈ = a₆;

a₅ = a₄; a₈ = a₇;

a₅ = a₅; a₈ = a₈.

Например, для a₅ имеем:

Рис. 5.3

А – мажоритарный элемент, который выдает 0 или 1 в зависимости от того, чего больше на его входе. Если сумма нулей больше, чем сумма единиц, то он выдаст ноль и наоборот.

Аналогичная схема составляется для a₈.

35. Циклический код. Математическое введение. Выбор образующего многочлена по требуемой корректирующей способности кода.

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

Циклические коды незаменимы при необходимости передавать информацию в каналах связи, в которых отсутствует возможность повторной передачи данных. Циклические коды применяются при записи и считывании на HDD, CD и DVD, при использовании USB-портов для обмена информацией, при передаче аудио и видео информации.

Разрешенную кодовую комбинацию Ц.К. можно рассматривать как элемент подмножества множества многочленов степени не выше (n – 1). Для анализа Ц.К. используется аппарат теории колец.

Коммутативным кольцом называется множество, в котором определены две операции: сложение и умножение.

Обе коммутативны, то есть:

; ;

ассоциативны, то есть:

; ;

и связаны законом дистрибутивности:

.

Чтобы наше замкнутое множество многочленов (n – 1) степени образовало кольцо, определим правила выполнения этих операций:

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

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

• умножение осуществляется по обычным правилам с приведением подобных членов путем сложения по модулю два;

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

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

.

После сдвига, соответствующего умножению на x, получим: , что недопустимо, так как x⁷ имеет степень более разрешенной x^n–1, в данном случае соответствует x⁶.

Поделим на многочлен .

Получим в остатке R(x):

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

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

Количество элементов в идеале зависит от вида g(x).

1. Если g(x) = 0, то в идеале всего один элемент «0».

2. Если g(x) = 1, то в идеал входят все элементы кольца.

3. Если g(x) многочлен степени m = n – k, то число элементов в идеале – 2^k. Эти элементы и есть искомый нами Ц.К.

Поэтому построение Ц.К. сводится к выбору образующего многочлена g(x) с заданными корректирующими способностями.

Требования к образующему многочлену Ц.К.

Разрешенная кодовая комбинация Ц.К. должна делиться на g(x) без остатка. Для этого необходимо, чтобы на g(x) делились все многочлены образующей матрицы кода. Каждая строка матрицы получается циклическим сдвигом образующего многочлена g(x) с приведением по модулю . Поэтому i-тую строку матрицы ƒ_i(x) можно записать:

,

где c = 1, если максимальная степень многочлена больше (n – 1);

c = 0, если имеет степень < n.

делится на g(x) без остатка.

Поэтому, чтобы ƒ_i(x) делилось на g(x) без остатка, необходимо, чтобы делилось на g(x) тоже без остатка.

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

Наибольшее число остатков дает неприводимый многочлен степени «m », когда m; n и k связаны между собой условиями: m = n – k, а n = 2^m – 1. Рассмотрим выбор g(x) в разных условиях.

Число проверочных разрядов – «m » и вид образующего многочлена g(x) зависят от числа ошибок, которые необходимо исправлять.

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

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