ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 309
Скачиваний: 7
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
129 описывается вектором ошибки ???? = (????
0
, ????
1
, … , ????
????−1
). Для двоичных кодов
????
????
=
0, 1
. В приведенном примере
???? = (1111), ???? = 1.
Модульная ошибка – это частный случай пакетной ошибки. В литературе по кодированию ее называют байтовой ошибкой. Модуль ошибок – это фазиро- ванный пакет ошибок. В этом случае граница (фаза) пакета известна. Длина мо- дуля ошибок и кратность модуля ошибок обозначаются соответственно ???? и ????.
Число возможных конфигураций векторов ошибок равно 2
????
− 1. Для ???? = 4 кон- фигурации ошибок образуют следующее множество векторов ошибок:
???? =
[
1 0 0 0
0 1 0 0
1 1 0 0
1 1 1 1]
Пусть двоичная информация
0001 0110 1111 1010 записывается в ЗУ с модульной ошибкой. Вектор ???? = (1010), q = 1. Тогда на выходе ЗУ поток представляется в виде
1011 0110 1111 1010.
В реальных системах модульные и пакетные ошибки встречаются чаще, чем отдельно расположенные ошибки. Зависимые ошибки могут вызываться ис- точником периодического шума, например, расположенным поблизости радио- локатором или каким-то вращающимся электромеханизмом, замираниями в ли- нии связи и пр. В этом случае необходимо применение кодов, исправляющих па- кетные и модульные ошибки. Заметим, что при наличии таких ошибок может оказаться более правильным использовать процедуру перемежения порядка сим- волов в закодированной последовательности перед передачей, и восстановления исходного порядка символов после приема с тем, чтобы рандомизировать ошибки, объединенные в пакеты.
7.2.4. Контроль ошибок
Кодовое слово можно представить в виде вектора с координатами в n- мерном векторном пространстве. Например, для ???? = 3 вектор ???? = (????
0
????
1
????
2
) находится в трехмерном евклидовом пространстве (рис. 7.2).
130
Разрешеннымисловами для передачи выбраны векторы ????
1
= (0 0 0) и ????
2
=
= (1 1 1).
Рис. 7.2. Трехмерный куб
Рис. 7.2 наглядно иллюстрирует алгебраическую интерпретацию понятия
«мощность кода»:
1. Кодовые слова полного кода определяют n-мерное пространство, состо- ящее из ????
????
последовательностей. При
???? = 2 трехмерное пространство включает восемь последовательностей полного двоичного кода.
2. Кодовые слова избыточного кода определяют подпространство (подмно- жество) n-мерного пространства. При ???? = 2 трехмерное подпространство вклю- чает ????
????
последовательностей двоичного кода.
Под воздействием помех происходит искажение отдельных разрядов век- тора разрешенного подмножества. В результате разрешенные для передачи ко- довые векторы переходят в другие векторы (с иными координатами) – запрещен- ные. Факт перехода разрешенного слова в запрещенное можно использовать для контроля над ошибками.
Возможна ситуация, когда разрешенный вектор переходит в другой разре- шенный кодовый вектор: (0 0 0)
(1 1 1). В этом случае ошибки не обнаружи- ваются, и контроль становится неэффективным.
Из рассмотренной модели можно сделать следующий очевидный, но важ- ный вывод. Для того, чтобы передаваемые векторы можно было бы отличать друг от друга при наличии помех, необходимо располагать эти векторы в n- мерном пространстве как можно дальше друг от друга.
Из этой же модели следует геометрическая интерпретация расстояния
Хэмминга: ????
????
– это число ребер, которые нужно пройти, чтобы перевести один вектор в другой, т. е. попасть из вершины одного вектора в вершину другого.
100 110 111 010 001 101
X
0
X
1
X
2
131
7.2.5. Кодовое расстояние кода и его связь с корректирующей
способностью
7.2.5.1. Обнаружение ошибок
Стратегия обнаружения ошибок в переданном слове заключается в следу- ющем. Можно обнаружить ошибку, если установить, что переданным словом было ближайшее по расстоянию Хэмминга к принятому слову. Покажем приме- нение этого утверждения.
П р и м е р 7 . 4 . Пусть
???? = 3, ???? = 2. Разрешенным для передачи является множество кодовых слов:
???? =
[
0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1]
Очевидно, что код ???? имеет ???? = 1. Любая одиночная ошибка трансформи- рует слово кода в другое разрешенное для передачи слово. Это случай, когда вы- бранное для передачи информации множество слов не обладает корректирую- щей способностью.
Пример 7 .5. Пусть теперь подмножество ???? разрешенных для передачи кодовых слов представлено в виде двоичных векторов с четным весом (четным числом единиц):
???? = [
0 0 0 1
1 0 1
0 1 0
1 1
].
Заданный код ???? имеет ???? = 2. Запрещенные кодовые слова представлены в виде подмножества
???? = [
1 0 0 0
1 0 0
0 1 1
1 1
].
Если ???? = 2, то ни одно из разрешенных кодовых слов (т. е. кода ???? ) при одиночной ошибке не переходит в другое разрешенное слово этого же кода.
132
Таким образом, код ???? обнаруживает:
одиночные ошибки;
ошибки нечетной кратности (для ???? = 3 – тройные).
Например, тройная ошибка кодового слова x = (110) при векторе ???? =
= (111) переводит его в запрещенный вектор
???? = ????⨁???? = (001).
Рассмотрим процесс декодирования в режиме обнаружения.
Допустим, передавалось кодовое слово x = (101). Возникла одиночная ошибка, вектор которой ???? = (100). На вход декодера поступил вектор ???? =
= ????⨁???? = (001). Данный вектор принадлежит запрещенному подмножеству ????.
Следовательно, декодер устанавливает, что при передаче информации произо- шла ошибка. Таким образом, осуществляется контроль ошибок.
Еще раз рассмотрим утверждение: переданным словом было то, которое является ближайшим по расстоянию Хэмминга к принятому. Вычислим рассто- яния Хэмминга для всех слов разрешенного подмножества и входным вектором: dist
1
(000, 001) = 1, dist
2
(101, 001) = 1, dist
3
(011, 001) = 1, dist
4
(110, 001) = 3.
Наиболее вероятно, что передаваемыми могли быть следующие слова:
????
1
= (000), ????
2
= (101), ????
3
= (011).
Вывод. В общем случае, при необходимости обнаруживать ошибки крат- ностью t кодовое расстояние кода должно удовлетворять выражению
d
t + 1. (7.2)
7.2.5.2. Исправление ошибок
Пример 7 .6. Пусть n = 3, q = 2; код G задан векторами x
1
= (000) и x
2
=
= (111). При возникновении одиночных ошибок или множества векторов
???? = [
1 0 0 0 1 0 0 0 1
].
Кодовому слову x
1
= (000) соответствует следующее запрещенное подмно- жество:
???? = {????
1
⊕ ????} = [
1 0 0 0 1 0 0 0 1
].
133
Kодовому слову x
2
= (111) соответствует следующее запрещенное подмно- жество:
???? = {????
2
⊕ ????} = [
0 1 1
1 0 1
1 1 0
].
Таким образом, коду G, разрешенному для передачи подмножеств векто- ров ????
1
, ????
2
, соответствуют два запрещенных подмножества векторов
A
и
L
:
???? = [
0 0
0 1
1 1
]
⟶[
1 0 0
0 1 0
0 0 1
]=????
⟶[
0 1 1 1 0 1 1 1 0
]=????
Стратегия исправления ошибок заключается в следующем:
каждая из одиночных ошибок приводит к запрещенному кодовому слову того или иного запрещенного подмножества (L и A);
структура кодового запрещенного подмножества, относящаяся к соот- ветствующему исходному разрешенному подмножеству, позволяет определить местоположение ошибки, т. е. исправить ошибку.
Допустим, передавалось кодовое слово ????
2
= (111). Возникла одиночная ошибка, вектор которой???? = (100). На вход декодера поступил вектор
???? = ????⨁???? = (011).
Вычислим расстояния Хэмминга для всех слов разрешенного подмноже- ства и входным вектором: dist
1
(000, 011) = 2, dist
2
(111, 011) = 1.
Наиболее вероятно, что передавалось слово
????
2
= (111).
Для исправления ошибок кратностью ???? кодовое расстояние должно удо- влетворять соотношению
d
2
???? +1.
(7.3)
Используя эту формулу, можно записать
???? =
(d – l)/2
, где
l
– целая часть числа l.
134
8. АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ
Основой построения наиболее важных известных кодов, корректирующих ошибки, является их алгебраическая структура. Существование особых струк- турных закономерностей в строении таких кодов желательно по двум причинам:
‒ они облегчают изучение свойств кода;
‒ обеспечивают возможность практической реализации кодов на аппа- ратно ‒ программном уровне.
Теория групп, колец, полей ‒ это те понятия конечной алгебры, которые являются основой для поиска хороших кодов, контролирующих ошибки. Эти же алгебраические структуры используются при технической реализации методов криптографической защиты информации, алгоритмов криптоанализа. Математи- ческие основы названных понятий широко применяются в алгоритмах дискрет- ных преобразований цифровой обработки сигналов и изображений.
1 ... 7 8 9 10 11 12 13 14 ... 17
8.1. Группы
8.1.1. Арифметика конечных групп
Определение 8.1. Группа ‒ это алгебраическая структура или множество элементов ???? с заданной на нем основной алгебраической операцией.
Замечания:
1. В большей части это те же операции, которые применимы к числовым системам;
2. Для теории кодирования наибольшее значение имеют бинарные опера- ции.
Элементы множества произвольной природы обозначают как ???? = {????, ????, ????}, а результат операции символически записывают в виде ???? = ????(????, ????). Говорят: на множестве ???? задана бинарная операция ????. Чтобы подчеркнуть абстрактность операции применяют символы ∗ или ∘. При операции сложения пишут ???? = ???? +
????, а при операции умножения ???? = ???? · ????.
Замечание. Операции вычитания и деления это неосновные операции, так как они являются обратными для сложения и умножения.
Алгебраические операции могут задаваться таблицами Кэли. Первые строка и столбец таблицы состоят из элементов множества ????. Результат опера- ции записывается в ячейке таблицы с координатами, задаваемыми элементами множества. Например, для множества элементов ???? = {????, ????} операцию можно представить в виде таблицы
????
????
????
????
????
????
????
????
????
135
В группе должны выполняться следующие аксиомы:
1) замкнутость ‒ любой паре
????, ???? элементов из множества ???? ставится в однозначное соответствие третий элемент ???? ∈ ????, т. е. ????∗???? = ????
2) ассоциативность ‒ для всех элементов множества ???? ={????, ????, ????} выполня- ется
????∗(????∗????)=( ????∗????)∗????= ????∗????∗????;
3) существование во множестве ???? нейтрального элемента ????, такого, что вы- полняется
????∗???? = ????∗???? = ???? ∈ ????;
4) существование для каждого элемента ???? ∈ ???? обратного ????̂ или ????
‒1
∈ ????, такого, что ???? ∗ ????̂ = ????̂ ∗ ???? = ???? или ???? ∗ ????
‒1
= ????
‒1
∗ ???? = ????;
5) если в группе выполняется аксиома коммутативности, т. е. для любых ???? и ???? из группы ????∗???? = ????∗ ????, то группа называется коммутативной, или абелевой
(N. Abel (1802 ‒ 1829), норвежский математик).
Определение 8.2. Если группа содержит конечное число элементов, то она называется конечной группой, а число элементов в группе называется порядком группы. Если порядок группы бесконечен, то она называется бесконечной.
Замечания:
1. Аддитивная абелева группа в качестве нейтрального элемента
???? имеет
0,
???? + ????̂ = ???? = 0.
2. Мультипликативная абелева группа в качестве нейтрального элемента ???? имеет 1, ???? · ????̂ = ???? = 1.
Теорема 8.1. Единичный элемент в группе является единственным. Для каждого элемента группы обратный элемент также является единственным.
Рассмотрим примеры абелевых групп.
Пример 8 .1 . Рациональные числа относительно операции сложения <
????; +>.
Пример 8.2. Натуральные числа относительно операции умножения <
ℕ; · >.
Пример 8 .3. Совокупность действительных чисел относительно опера- ции сложения < ℝ; +>.
Пример 8. 4. Группа из одного элемента (единичного) < ????;∗>, например,
< 0; +>‒ аддитивная, < 1;·> ‒ мультипликативная.
Пример 8 .5. Группа второго порядка. Ее таблица Кэли имеет вид
136
Здесь ???? ∗ ????̂ = ????. Выражение (???? ∗ ????) не может быть равным ????, т. к. в группе может быть только один нейтральный элемент.
На множестве из двух элементов групповая операция задается не более чем одним способом. Например, аддитивная абелева группа второго порядка <
{0,1}; +; 0 > задается таблицей Кэли
Для элемента 0 обратным является 0; для элемента 1 обратным является 1, так как в группе может быть только один нейтральный элемент, который полу- чается из определения ???? ∗ ????̂ = ????.
Мультипликативная абелева группа второго порядка < {1, −1}; ·; 1 > зада- ется таблицей Кэли
Для элемента 1 обратным является 1; для элемента (– 1) обратным является
(–1), т. к. в группе может быть только один нейтральный элемент, который полу- чается из определения ???? ∗ ????̂ = ????.
Пример 8.6. На множестве из трех элементов групповая операция зада- ется не более чем одним способом. Например, группа третьего порядка <{????, ????,
????}; +; ????>задается таблицей Кэли (Табл. 8.1).
Таблица 8.1
Таблица Кэли для группы <{????, ????, ????}; +; ????>
Табл. 8.1 обладает следующими свойствами:
1) из однозначности разрешимости уравнения ???? ∗ ???? = ???? (у каждого эле- мента ???? из множества ???? существует единственный обратный элемент) следует,
???? e
????
e e
????
????
????
e
+
0 1
0 0
1 1
1 0
·
1
‒1 1
1
‒1
‒1
‒1 1
+
????
????
????
????
????
????
????
????
????
????
????
????
????
????
????
137 что в каждой строке (в каждом столбце) содержатся все элементы группы по од- ному разу;
2) строки и столбцы ее являются перестановками последовательности
(
????, ????, ????);
3) все строки (столбцы) различны.
Другой пример группы <{0, 1, 2}; +; 0> на множестве из трех элементов задается следующей таблицей Кэли (табл. 8.2).
Таблица 8.2
Таблица Кэли для группы <{0, 1, 2}; +; 0>
Обратные элементы этой группы:
‒ для 1 обратным является элемент 2, т. к. 1 + 1
̂ =1 + 2 = 0;
‒ для 2 обратным является элемент 1, т. к. 2 + 2̂ = 2+1= 0.
Замечание. С точки зрения понятий конечной алгебры, рассмотренные группы (см. табл. 8.1 и табл. 8.2) следует считать однотипными. Этот факт при- водит к очень важному понятию алгебры ‒ изоморфизма. Из этого понятия стро- ятся изоморфные коды.
Пример 8 .7 . Совокупность двоичных n-разрядных чисел с операцией сложения по модулю 2 (mod 2 ) образует группу. Например, в группе
< {???? = (1110010), ???? = (1100101)}; ⊕; 0 > операция
???? ⊕ ???? = (0010111).
В такой группе ???? = (0000000). Обратный элемент равен самому себе, т. к.
???? ⊕ ????̂ = ???? = (0000000). Для ???? = (1110010) обратный элемент ????̂ = (1110010).
Пример 8 .8 Пример неабелевой группы. Совокупность невырожденных матриц порядка ???? относительно матричного умножения ???? · ???? ≠ ???? · ????.
Замечание. Существует матрица порядка ????, которая коммутирует с любой матрицей такого же порядка. При умножении на нее действие аналогично умно- жению на нейтральный элемент (единичный элемент), т. е. ???? · ???? = ???? · ???? =
= ????. Это будет иметь место в том случае, когда ???? будет единичной матрицей.
Например, для ???? = 4 матрица ???? имеет вид
+
0 1
2 0
0 1
2 1
1 2
0 2
2 0
1