Обработка информации в вычислительных системах невозможна без передачи сообщений между отдельными элементами (оперативной памятью и процессором, процессором и внешними устройствами). Примеры процессов передачи данных приведены в следующей таблице.
| Передатчик | Канал | Приемник | |
|---|---|---|---|
| Разговор людей | Голосовой аппарат человека | Воздушная среда. Акустические колебания | Слуховой аппарат человека |
| Телефонный разговор | Микрофон | Проводник. Переменный электрический ток | Динамик |
| Передача данных в сети Интернет | Модулятор | Проводник. |
Демодулятор |
| Радиотелефон, рация | Радиопередатчик | Эфир. Электромагнитные волны | Радиоприемник |
В перечисленных выше процессах передачи можно усмотреть определенное сходство. Общая схема передачи информации [31], [33], [32] показана на рис.7.1.
В канале сигнал подвергается различным воздействиям, которые мешают процессу передачи. Воздействия могут быть непреднамеренными (вызванными естественными причинами) или специально организованными (созданными) с какой-то целью некоторым противником. Непреднамеренными воздействиями на процесс передачи (помехами) могут являться уличный шум, электрические разряды (в т. ч. молнии), магнитные возмущения (магнитные бури), туманы, взвеси (для оптических линий связи) и т.п.
(рис 7.1) Общая схема передачи информации
Для изучения механизма воздействия помех на процесс передачи данных и способов защиты от них необходима некоторая модель. Процесс возникновения ошибок описывает модель под названием двоичный симметричный канал (ДСК) [32], [33], схема которой показана на рис.7.2.
(рис 7.2) Схема двоичного симметричного канала
При передаче сообщения по ДСК в каждом бите сообщения с вероятностью $$p$$ может произойти ошибка, независимо от наличия ошибок в других битах. Ошибка заключается в замене знака 0 на 1 или 1 на 0.
Некоторые типы ошибок:
Чаще других встречается замена знака. Этот тип ошибок исследован наиболее полно.
Если при кодировании сообщений используются оптимальные коды, то при появлении всего лишь одной ошибки все сообщение или его значительная часть может быть искажена. Рассмотрим пример. Пусть кодирование элементарных сообщений $$a_2a_3a_5a_1a_4$$ источника осуществляется с использованием кодовой таблицы
| Сообщения | Кодовое слово |
|---|---|
| $$a_1$$ | 00 |
| $$a_2$$ | 01 |
| $$a_3$$ | 10 |
| $$a_4$$ | 110 |
| $$a_5$$ | 111 |
Тогда закодированное сообщение имеет вид 011011100110. Если в первом знаке произойдет ошибка, то будет принято сообщение 111011100110, которое декодируется в слово $$a_5a_2a_4a_2a_3$$. Полное искажение сообщения из-за одной ошибки происходит вследствие того, что одно кодовое слово переходит в другое кодовое слово в результате замены одного или нескольких знаков. Пример показывает, что оптимальное кодирование плохо защищает сообщения от воздействия ошибок.
На практике необходим компромисс между экономностью кода и защитой от ошибок.
Сначала удаляется "бесполезная" избыточность (в основном статистическая), а затем добавляется "полезная" избыточность, которая помогает обнаруживать и исправлять ошибки.
Рассмотрим некоторые методы повышения надежности передачи данных. Широко известными методами борьбы с помехами являются следующие [34]:
Рассмотрим подробней каждый из этих способов.
Общим во всех этих способах повышения надежности является введение избыточности, то есть увеличение тем или иным способом объема передаваемого сообщения для возможности его правильной расшифровки при наличии искажений.
Следует отметить, что введение избыточности уменьшает скорость передачи информации, так как только часть передаваемого сообщения представляет интерес для получателя, а избыточная его доля введена для предохранения от шума и не несет в себе полезной информации.
Естественно выбирать такие формы введения избыточности, которые позволяют при минимальном увеличении объема сообщения обеспечивать максимальную помехоустойчивость.
Способы введения избыточности, позволяющие обнаруживать и исправлять ошибки, можно разделить на два класса, один из которых соответствует блоковым кодам, а другой - сверточным кодам [33]. Обе схемы кодирования применяются на практике. При блоковом кодировании последовательность, составленная из полученных в результате коди-рования источника кодовых слов, разбивается на блоки одинаковой длины. Каждый блок перед отправкой в канал обрабатывается независимо от других. Выход устройства, выполняющего сверточное кодирование, напротив, зависит не только от обрабатываемых в данный момент знаков, но и от предыдущих знаков. Остановимся более подробно на блоковом кодировании.
Как было показано ранее, ошибка в одном лишь разряде может испортить все сообщение. Чтобы избежать таких тяжелых последствий, сообщения, закодированные каким-либо экономным кодом, перед направлением в канал делятся на блоки одинаковой длины и каждый блок передается отдельно. При этом методы, позволяющие обнаруживать и исправлять ошибки, применяются к каждому блоку. Такой прием напоминает разделение большого судна на несколько изолированных друг от друга отсеков, что позволяет при пробоине в одном отсеке сохранить судно и груз в других отсеках.
Рассмотрим схему передачи данных, показанную на рис.7.3.
С кодирующего устройства в канал поступают закодированные блоки (кодовые слова) одинаковой длины $$n$$. В канале в результате действия различных помех в некоторых битах передаваемого сообщения могут происходить ошибки. Процедуру кодирования при передаче и
(рис 7.3) Схема передачи данных
декодирования при приеме с использованием одной и той же кодовой таблицы иллюстрируем рис.7.4. Предполагается, что появление ошибок описывается моделью дискретного симметричного канала
(рис 7.4) Использование кодовой таблицы для кодирования и декодирования
В геометрической интерпретации эти блоки можно рассматривать как точки n-мерного пространства $$B^n$$, где $$B=\{0, 1\}$$. Точки этого пространства представляют собой последовательности чисел 0 и 1 длины $$n$$. Пространства $$B^n$$ для $$n = 1, 2, 3$$ можно представить в виде угловых точек единичного интервала ($$n=1$$), вершин квадрата со стороной, равной 1 ($$n=2$$), и вершин куба с ребрами длины 1 ($$n=3$$). Эти пространства условно изображены на рис.7.5.
Код, используемый для обнаружения и исправления ошибок, представляет собой некоторое подмножество пространства $$B^n$$. В качестве примера можно привести код $$с=\{000\; 110\; 101\; 011\}\subset B^3$$. Кодовые слова этого кода как точки пространства $$B3$$ изображены на рис. 7.6 белыми кружками. Если представить куб расположенным в трехмерном пространстве, то словам данного кода соответствуют вершины тетраэдра. Более полезным
(рис 7.5) Геометрическое представление пространства Bn для n = 1, 2 и 3
с практической точки зрения является то, что каждое слово кода содержит четное число единиц. Если при передаче кодового слова через канал произойдет одна ошибка, то число единиц в слове станет нечетным. Проверяя свойство четности числа единиц в слове после получения его из канала на приемном конце, можно обнаружить одну ошибку. В данном случае для кодирования четырех знаков используется 3 двоичных разряда, хотя достаточно двух. Однако благодаря такой избыточности удается обнаружить одну ошибку.
(рис 7.6) Код в B3, обнаруживающий одну ошибку
В соответствии с общей схемой передачи сообщений в кодирующем и декодирующем устройствах используется одна и та же кодовая таблица и, следовательно, множество кодовых слов. При передаче кодового слова через канал возможны следующие ситуации.
Передавалось и было получено некоторое кодовое слово $$c_i$$. Эта ситуация, которая показана в верхней части рис.7.7, соответствует отсутствию ошибок при передаче.
Передавалось кодовое слово ci, а получено было сообщение, которое не является кодовым словом. При попытке декодировать это сообщение будет обнаружено, что такого слова в кодовой таблице нет. Это означает, что ошибка, произошедшая при передаче и исказившая кодовое слово, обнаружена. Эта ситуация изображена в средней части рис.7.7.
(рис 7.7) Возможные варианты передачи кодового слова через канал
В процессе передачи кодовое слово $$с_i$$ может так исказиться из-за ошибок, что оно превратится в другое кодовое слово $$с_j$$. В этом случае ошибка не обнаруживается, поскольку полученное сообщение также является кодовым словом, и декодирование будет выполнено неверно. Такая ситуация показана в нижней части рис.7.7.
Определение. Код обнаруживает $$t$$ ошибок, если $$\forall \; r \le t\; r$$ ошибок в кодовом слове переводит его в слово, которое не входит в код.
Код "Тетраэдр" из предыдущего примера обнаруживает одну ошибку (меняется четность), но не обнаруживает две ошибки. Например, слово 101 в результате двух ошибок в первых двух знаках переходит в другое кодовое слово (реализуется третий вариант передачи на рис.7.7). Легко заметить, что данный код обнаруживает 3 ошибки, 5 ошибок и вообще любое нечетное число ошибок, но не обнаруживает любое четное число ошибок. Поэтому, в соответствии с приведенным определением, этот код не обнаруживает 3 или 5 ошибок, а только одну.
В пространстве $$B^n$$ вводится мера отличия двух точек этого пространства, которая называется расстоянием Хеминга [29], [33], [34].
Определение. Расстоянием $$\rho(\alpha, \beta)$$, по Хемингу, между вершинами $$\alpha=\alpha_1\alpha_2 \dots \alpha_n \in B^n$$ и $$\beta=\beta_1 \beta_2 \dots \beta_n \in B^n$$ называется число разрядов, в которых эти вершины различаются.
В виде математической формулы это можно записывать так:
$$\rho(\alpha, \beta)=\sum_{i=1}^{n}|\alpha_i-\beta_i|$$где через $$|x|$$ обозначается
В качестве примера рассмотрим расстояние Хеминга между двумя точками (последовательностями или словами) $$\alpha=0110101$$ и $$\beta=1111001$$ пространства $$B^7$$. Эти последовательности отличаются в первой, четвертой и пятой позициях, следовательно, $$\rho(\alpha, \beta)=3$$.
Вещественную функцию $$d(x,y)$$ двух переменных на множестве $$V$$ принято называть расстоянием, если она обладает следующими свойствами:
$$d(x,y) \ge 0 \forall x, y \in V, d(x,y) =0 \mbox{\ тогда\ и\ только\ тогда,\ когда\ } x=y;\\ d(x,y) = d(y,x);\\ d(x,z) \le d(x,y) + d(y,z) (\mbox{неравенство треугольника}).$$Расстояние Хеминга обладает перечисленными выше свойствами. Два первых свойства очевидным образом следуют из определения расстояния Хеминга (или из приведенной выше формулы для расстояния Хеминга), а третье свойство вытекает из следующей последовательности равенств и неравенств
$$\rho(\alpha, \beta)=\sum_{i=1}^{n}|\alpha_i-\beta_i|=\sum_{i=1}^{n}|\alpha_i-\gamma_i+\gamma_i-\beta_i|\le \sum_{i=1}^{n}(|\alpha_i-\gamma_i|+|\gamma_i-\beta_i|)=\\ =\sum_{i=1}^{n}|\alpha_i-\gamma_i|+\sum_{i=1}^{n}|\gamma_i-\beta_i|=\rho(\alpha, \gamma)+\rho(\gamma, \beta)$$Возможности обнаруживать и исправлять ошибки с помощью кода C зависят от его характеристики, которая называется кодовым расстоянием [34].
Определение. Кодовым расстоянием $$т_C$$ кода $$C$$ называется минимальное расстояние между различными кодовыми словами (векторами).
$$\rho_c min_{\substack{\alpha, \beta \in C\\ \alpha \ne \beta}}\rho(\alpha, \beta)$$С использованием расстояния Хеминга в пространстве $$B^n$$ можно определить аналоги таких геометрических понятий, как сфера и шар [34]. Эти понятия потребуются в дальнейшем для объяснения принципов обнаружения и исправления ошибок с помощью кодов.
Сферой радиуса $$t$$ с центром в точке $$\alpha$$ является множество
$$S_{\alpha}^0=\{\beta \in B^n|\rho(\alpha, \beta)=t\}$$Число точек $$|S_{\alpha}^0(t)|$$ в сфере $$S_{\alpha}^0(t) $$ определяется выражением
$$|S_{\alpha}^0(t)|={n\choose t}=C_n^1$$Шаром радиуса $$t$$ с центром в точке $$\alpha$$ называется множество
$$S_{\alpha}(t)=\{\beta \in B^n|\rho (\alpha, \beta) \le t\}$$Число точек $$|S_{\alpha}(t)|$$ в шаре $$S_{\alpha}(t)$$ определяется выражением
$$|S_{\alpha}(t)|=1+{n\choose 1}+{n \choose 2}+\dots+{n\choose 1}$$Замечание. Если имеется некоторое исходное слово $$\alpha$$, а слово $$\beta$$ получилось из $$\alpha$$ в результате одной ошибки, произошедшей, например, при передаче слова $$\alpha$$ по каналу, то $$\rho(\alpha, \beta)=1$$, т. е. в смысле Хеминга расстояние между ними равно 1.
Аналогичным образом, если при передаче слова $$\alpha$$ произошло $$\kappa$$ ошибок и оно превратилось в слово $$\beta$$ то $$\rho(\alpha,\betar)=\kappa$$.
Утверждение. Код обнаруживает $$\tau$$ ошибок, если для любых кодовых слов $$\alpha$$ и $$\beta$$ $$(\forall \alpha, \beta \in C) \rho(\alpha, \beta) \ge t+1$$ или $$\rho_c \ge t+1$$.
Рассмотрим, как происходит декодирование сообщения после его передачи через канал. Если при передаче не произошло ошибок, то будет получено кодовое слово. Естественно считать это кодовое слово результатом декодирования.
Если в результате передачи получено не кодовое слово, то произошла ошибка. В этом случае целесообразно использовать декодирование в ближайшее кодовое слово. Такой подход имеет объяснение. Действительно, пусть полученное слово $$\delta$$ ближе к кодовому слову $$\alpha$$, чем к любому другому кодовому слову, т. е. $$\rho(\alpha, \delta) < \rho(\beta, \delta)$$ для всех кодовых слов $$b\ne a$$. Если сравнить различные гипотезы о том, какое исходное слово было пе-редано, то гипотеза о передаче слова $$\alpha$$ при условии получения слова $$\delta$$ является наиболее вероятной. Это следует из того, что первая гипотеза (основная) соответствует меньшему числу ошибок при передаче, чем конкурирующие гипотезы.
Утверждение. Код исправляет $$t$$ ошибок, если для любых кодовых слов $$\alpha$$ и $$\beta (\forall \alpha, \beta \in C) \rho(\alpha, \beta) \ge 2t+1$$ или $$\rho_c \ge 2t+1$$.
Для доказательства рассмотрим шары радиуса $$t$$ с центрами в кодовых словах. Из неравенства треугольника для расстояния Хеминга следует, что эти шары не пересекаются. Тогда при передаче любого кодового слова и при числе ошибок, не превышающем $$t$$, полученное слово будет находиться в шаре с центром в передаваемом слове и декодироваться (по методу декодирования в ближайшее кодовое слово) в переданное слово.
Из последних двух утверждений следует, что важнейшей характеристикой кода, определяющей его корректирующие возможности, является его кодовое расстояние.
Рассмотрим, следуя [34], какие задачи требуется решать при создании кодов, с помощью которых можно эффективно обнаруживать и исправлять ошибки, возникающие при передаче сообщений. Одна из важнейших задач теории кодирования состоит в следующем. Требуется построить код, исправляющий $$t$$ ошибок и имеющий максимально возможное число точек. В геометрической постановке эта же задача звучит следующим образом: среди вершин единичного $$n$$-мерного куба $$B^n$$ требуется выделить максимальное число таким способом, чтобы расстояние между любыми двумя
Другая, связанная с предыдущей, задача состоит в расположении $$s$$ точек в вершинах $$B^n$$ так, чтобы наименьшее из попарных расстояний между ними было возможно большим. Это расстояние обозначается через $$d(s, n)$$.
Выражения "построить", "выделить", "расположить" нуждаются в уточнении, так как нам вовсе не безразлично, в каком виде будет задан искомый код. Самый простой способ - перечисление всех кодовых точек - является неэффективным, требует большой памяти. Поэтому нужен такой способ задания кода, который позволяет просто восстановить каждую точку кода по ее номеру. Другими словами, код должен иметь простую реализацию. С некоторыми просто реализуемыми кодами мы познакомимся ниже. С другой стороны, мы хотим иметь возможность просто восстанавливать исходное сообщение на выходе.
Таким образом, "хороший код" должен удовлетворять следующим трем естественным требованиям:
Следует отметить, что эти требования в значительной степени являются противоречивыми, так как код $$c$$, исправляющий много ошибок, вовсе не обязан иметь простую реализацию и тем более простой алгоритм декодирования. Поэтому на практике применяются коды, которые обладают в достаточной мере всеми тремя перечисленными выше качествами.
$$A(n,s)$$ - максимальное число точек кода в $$B^n$$, расстояние между любыми двумя кодовыми словами не меньше $$s$$.
Для количественной оценки свойств кода полезно знать, насколько его параметры отличаются от параметров "идеального" кода. Для этого необходимо иметь хотя бы приближенные значения важнейших параметров "идеального" кода, т. е. значения $$A(n, 2t+1)$$ и $$d(s, n)$$. Следует отметить, что функции $$A(n, 2t+1)$$ и $$d(s, n)$$ не являются единственными параметрами, характеризующими качество кода. Не менее важными являются также такие параметры кода, как вероятность правильного декодирования и вероятность обнаружения ошибки. Имеется также еще ряд других важных критериев, применяющихся для оценки качества кодов.
Если расстояние между любыми двумя точками кода не меньше, чем $$2t+1$$, то шары радиуса $$t$$ с центрами в кодовых словах не пересекаются. Поэтому общее число точек в этих шарах равно: $$|V|*(1+C_n^1+C_n^2+\dots+C_n^t)$$, где $$|V|$$ - число точек (кодовых слов) в коде $$V$$, а $$ (1 + С_n^1 + С_n^2 +\dots + С_n^t)$$ число точек в шаре радиуса $$t$$. Так как число точек, попавших в шары, очевидно, не превосходит общего числа точек (двоичных слов) в $$B^n$$, то $$\V\*(1+C_n^1+C_n^2+\dots+C_n^t)\le 2^n$$. Это неравенство справедливо для любого множества с расстоянием между любыми двумя точками не меньше, чем $$2t+1$$, в том числе и для кода с максимальным числом слов $$A(n, 2t+1) $$, откуда и следует неравенство Хеминга.
$$A(n,2t+1) \le \frac{2^n}{(1+C_n^1+C_n^2+\dots+C_n^t)}$$Для максимального числа слов $$A(n, 2t+1) $$ в коде, исправляющем $$t$$ ошибок, может быть получена оценка снизу.
Утверждение (неравенство Варшамова - Гилберта):
$$\frac{2^n}{(1+C_n^1+C_n^2+\dots+C_n^{2t})}\le A(n,2t+1)$$Чтобы доказать неравенство Варшамова - Гилберта, можно рассмотреть следующую процедуру построения кода, исправляющего $$t$$ ошибок.
В качестве первого кодового слова возьмем произвольное слово (вектор) из $$B^n$$. Рассмотрим шар радиуса $$2t$$ с центром в данном слове. Если в $$B^n$$ есть слова, не вошедшие в этот шар, то в качестве второго кодового слова выберем любое из них. В качестве третьего кодового слова выберем любое слово, не вошедшее ни в один из построенных ранее шаров. Построим шар радиуса $$2t$$ с центром в данном слове. Продолжим эту процедуру выбора кодовых слов и построения шаров до тех пор, пока не будут исчерпаны все точки пространства $$B^n$$. Предположим, построение кода завершилось за $$m$$ шагов. После завершения этой процедуры пространство $$B^n$$ будет покрыто $$m$$ построенными шарами, содержащими по $$1+С_n^1+С_n^2+\dots+С_n^{2t}$$ точек каждый. Поскольку шары могут пересекаться, справедливо неравенство $$т*(1+С_n^1 + С_n^2 +\dots+С_n^{2t}) \ge 2^n$$. Центры шаров образуют код $$C$$, имеющий, как следует из способа построения, кодовое расстояние $$\rho_C \ge 2t+1$$. Из того, что $$A(n, 2t +1) $$- это максимально возможное число точек кода с кодовым расстоянием не меньше, чем $$2t+1$$, следует, что $$A(n, 2t+1)\ge m$$ и $$А(п, 2t+1)*(1+С_n^1+С_n^2+\dots+С_n^{2t})\ge 2^n$$ . Последнее неравенство эквивалентно неравенству Варшамова - Гилберта.
Одним из подходов к регулярному построению кодов является применение в качестве кодовых множеств линейных подпространств [29], [33], [34]. Одно из преимуществ такого подхода заключается в хорошо изученной структуре подпространств линейных векторных пространств.
Для построения кодов, обнаруживающих и исправляющих ошибки, используются векторные пространства над конечным полем $$GF(2)$$ [32]. В этом случае множество ($$n$$-мерный куб) $$B^n$$ рассматривается как линейное векторное пространство над конечным полем $$GF(2)$$. Точки из $$B^n$$ становятся векторами, их можно складывать и умножать на числа из поля $$GF(2)$$.
Специфика некоторых понятий линейной алгебры в векторном пространстве $$B^n$$ является следствием особенностей поля $$GF(2)$$. Сложение векторов из $$B^n$$ производится покоординатно с учетом особенностей операции сложения в поле $$GF(2)$$.
Сложение и умножение в поле определяется следующими таблицами.
| $$\oplus$$ | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| $$\times$$ | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 0 | 1 |
Сложение в поле $$GF(2) $$ (сложение по модулю 2) часто обозначается $$\oplus$$. Этим же знаком будем обозначать сложение векторов из $$B^n$$. Следует отметить справедливое для всех векторов $$\alpha \in B^n$$ равенство $$\alpha \oplus \alpha = 0$$, вытекающее из таблицы сложения. Оно означает, что любой вектор является противоположным себе $$\alpha =-\alpha$$, а также что при заданных $$\alpha$$ и ($$\beta$$ уравнение имеет решение $$\chi = \alpha \oplus \beta= \beta \oplus \alpha$$.
Рассмотрим особенности еще некоторых понятий линейной алгебры.
Линейная комбинация в $$B^n$$. Учитывая, что $$B^n$$ рассматривается как векторное пространство над конечным полем $$GF(2)$$, содержащим только два элемента 0 и 1,
Линейная оболочка множества векторов из $$B^n \; v_{j_1}, v_{j_2}, \dots, v_{j_k}$$ - это совокупность различных сумм этих векторов. Линейная оболочка векторов $$\alpha, \beta, \dots, \gamma$$ будет обозначаться через $$ [\alpha, \beta, \dots, \gamma]$$.
Линейная зависимость векторов из $$B^n$$. Векторы $$v_{j_1}, v_{j_2}, \dots, v_{j_k}$$линейно зависимы, если существует сумма некоторых из них, равная 0.
Векторы $$v_{j_1}, v_{j_2}, \dots, v_{j_k}$$линейно независимы, если любая сумма некоторых из них не равна 0.
Утверждение. Если векторы $$v_{j_1}, v_{j_2}, \dots, v_{j_k}$$ независимы, то все их линейные комбинации (суммы) различны.
Доказательство. Предположим, что $$v_{j_1}, v_{j_2}, \dots, v_{j_k}=v_{j_1}, v_{j_2}, \dots, v_{j_m}$$ Удалив из левой и правой частей этого равенства одинаковые векторы и перенеся оставшиеся из правой части в левую, получим нулевую сумму векторов. Это противоречит их линейной независимости.
Всего из $$m$$ линейно независимых векторов можно составить
$$1+m+{m \choose 2}+\dots+{m \choose m}=2^m$$линейных комбинаций, и все они различны.
Из доказанного утверждения следует, что линейная оболочка $$m$$ линейно независимых векторов содержит $$2^m$$ вектора.
Рассмотрим пример. Пусть имеем два вектора
$$\alpha_1=\begin{pmatrix}1\\0\\0\end{pmatrix},\; \alpha_2=\begin{pmatrix}1\\1\\1\end{pmatrix}$$ $$\alpha_1=\begin{pmatrix}1\\0\\0\end{pmatrix},\; \alpha_2=\begin{pmatrix}1\\1\\1\end{pmatrix}\; \alpha_3=\begin{pmatrix}0\\1\\1\end{pmatrix},\; \alpha_4=\begin{pmatrix}0\\0\\0\end{pmatrix}$$Их линейная оболочка $$[\alpha_1, \alpha_2]$$ состоит из четырех векторов На традиционном изображении $$B^3$$ в виде точек куба $$\alpha_1, \alpha_2, \alpha_3, \alpha_4$$ образуют плоскость (увеличенные светлые вершины куба на рисунке).
(рис )
Подпространства в $$B^n$$. Подпространством векторного пространства $$B^n$$ называется подмножество векторов из $$B^n$$, замкнутое относительно операций сложения и умножения на число из поля $$GF(2)$$. Линейная оболочка $$[\alpha, \beta, \dots \gamma]$$ векторов $$\alpha, \beta, \dots, \gamma$$ уявляется подпространством пространства $$B^n$$.
Например, рассмотренная в предыдущем примере линейная оболочка из четырех векторов является подпространством, а множество векторов
$$\beta_1=\begin{pmatrix}1\\0\\0\end{pmatrix},\; \beta_2=\begin{pmatrix}1\\1\\1\end{pmatrix}\; \beta_3=\begin{pmatrix}0\\0\\1\end{pmatrix},\; \beta_4=\begin{pmatrix}0\\0\\0\end{pmatrix}$$подпространством не является, поскольку оно не замкнуто относительно операции сложения. Например, $$\beta_1+\beta_2$$ не входит в это множество векторов.
По аналогии с подпространствами в $$R^n$$ подпространства в $$B^n$$ могут задаваться
Нормой вектора $$\alpha \in B^n$$ называется число $$||\alpha||$$ единичных координат этого вектора. В кодировании
Кодовое расстояние линейного кода может быть вычислено проще, чем кодовое расстояние произвольного кода. Учитывая, что для слов $$\alpha \in C, \beta \in C$$ линейного кода $$C$$ справедливо $$\alpha \oplus \beta \in C$$, выполняется следующая цепочка равенств
$$р_с =min_{\alpha \ne \beta}\rho (\alpha, \beta) = min_{\alpha \ne \beta}||\alpha \oplus \beta||=min_{\gamma \in C}||\gamma||$$Определение. Пусть $$H$$ - матрица над полем $$GF(2)$$ размера $$ (n-k)\times n$$ и ранга $$(n-k)$$. Множество $$C \subset GF^n(2)$$ решений уравнения $$Hx=0$$ называется линейным $$(n,k)$$ кодом. $$H$$ - проверочная матрица, $$n$$ - длина кода, $$k$$ - размерность кода. Если матрица $$H$$ имеет вид $$H=(A E_{n-k})$$, где $$E_{n-k}$$ -
Рассмотрим, как можно получить линейный код, зная порождающую матрицу. Для этого решим уравнение $$Hx=0$$ и найдем кодовые слова. В матричном виде уравнение для кодовых слов запишется в виде
$$Hx=n-k\{(\overbrace{A}^{k} \overbrace{E_{n-k}}^{n-k})*\begin{pmatrix}x_1\\\vdots\\x_k\\x_{k+1}\\\vdots\\x_n\end{pmatrix}=A*\begin{pmatrix}x_1\\x_2\\\vdots\\x_k\end{pmatrix}+E_{n-k}*\begin{pmatrix}x_{k+1}\\x_{k+2}\\\vdots\\x_n\end{pmatrix}=A*\begin{pmatrix}x_1\\x_2\\\vdots\\x_k\end{pmatrix}+\begin{pmatrix}x_{k+1}\\x_{k+2}\\\vdots\\x_n\end{pmatrix}=0\\ \begin{pmatrix}x_{k+1}\\x_{k+2}\\\vdots\\x_n\end{pmatrix}=-A*\begin{pmatrix}x_1\\x_2\\\vdots\\x_k\end{pmatrix}$$Чтобы найти решение, нужно произвольно задать $$k$$ компонент $$x_1= u_1, x_2=u_2,\dots , x_k = u_k$$ вектора $$x$$, а остальные вычислить по формуле (2.6). Таким образом, первые $$k$$ компонент вектора $$x$$ полностью его определяют
$$\begin{pmatrix}u_1\\u_2\\\vdots\\u_k\\x_{k+1}\\x_{k+2}\\\vdots\\x_n\end{pmatrix}={E_k \choose -A}*\begin{pmatrix}u_1\\u_2\\\vdots\\u_k\end{pmatrix}$$Матрица $$G={E_k \choose -A}$$ называется порождающей. Ее столбцы образуют базис пространства решений системы $$Hx=0$$. Учитывая особенности поля $$GF(2)$$, порождающая матрица имеет вид $$G ={E_k \choose A}$$.
Нетрудно показать, что справедливо равенство $$H *G=O$$, где $$O$$ - матрица из нулевых элементов, имеющая $$n-k$$ строк и $$k$$ столбцов.
Для того чтобы лучше понять свойства
Свойства
Лемма. Линейный код $$C$$ с проверочной матрицей $$H_C$$ имеет кодовое расстояние $$\rho_{C_s} \ge s +1$$ тогда и только тогда, когда любые s столбцов матрицы $$H_C$$ линейного кода $$C$$ линейно независимы.
Если любые $$s$$ столбцов матрицы $$H_C$$ линейно независимы, то никакой вектор $$x=(x_1, x_2, \dots, x_n)^T$$, имеющий $$s$$ или менее ненулевых (единичных) компонент, не обращает в ноль произведение $$H_c * x =h_1x_1+h_2x_2+\dots h_nx_n$$. Это означает, что нормы всех кодовых слов, то есть слов $$z$$, для которых справедливо $$H_C*z=0$$, больше $$s$$, и следовательно, кодовое расстояние $$\rho_C \ge s+1$$.
Пусть теперь линейный код $$C$$ с проверочной матрицей $$H_C$$ имеет кодовое расстояние $$\rho_C \ge s+1$$. Для доказательства линейной независимости любых $$s$$ столбцов проверочной матрицы $$H_C$$ предположим противное, то есть предположим, что существует $$t<s$$ линейно зависимых столбцов матрицы $$H_C$$ Это значит, что сумма $$h_{i_1}+h_{i_2}+ \dots h_{i_k}k \le t < s$$ некоторых из этих столбцов равна нулевому вектору пространства $$B^n$$. Эту сумму можно представить как произведение $$h_{i_1}+h_{i_2} +\dots h_{i_k}, =H_c*x$$, где $$x$$ - вектор, у которого компоненты с номерами $$i_1, i_2, \dots, i_k, k \le t < s$$ равны 1, а остальные компоненты равны 0. Значит $$x$$ - кодовый вектор с нормой $$k<s$$, что противоречит тому, что кодовое расстояние $$\rho_C \ge s+1$$.
Рассмотрим некоторые примеры
Код с разрядом для проверки на четность является
или
$$х_4=х_1+х_2+х_3, $$то есть четвертый разряд (проверочный), равный сумме трех информационных, делает сумму всех разрядов кодового слова четной. Каждый столбец проверочной матрицы линейно независим, поэтому из доказанной выше леммы следует, что код имеет кодовое расстояние, равное 2, и следовательно, обнаруживает одну ошибку. Ошибка обнаруживается, если число единичных разрядов в принятом слове нечетно (сумма всех разрядов принятого слова по модулю 2 не равна 0). В этом коде 8 кодовых слов.
Код с повторением является
Линейное уравнение, определяющее код, в данном случае имеет вид
$$\begin{cases}\begin{matrix} x_1+x_2=0\\ x_1+x_3=0\\ x_1+x_4=0 \end{matrix} \end{cases}$$а его решения описываются соотношениями $$х_2=х_1,х_3=х_1,х_4=х_1$$. Эти равенства означают, что три проверочных разряда повторяют один информационный разряд. Любые 3 столбца проверочной матрицы являются линейно независимыми (сумма любых трех столбцов не равна нулевому столбцу), поэтому кодовое расстояние, равное 4, обеспечивает исправление одной ошибки и обнаружение трех. Код содержит всего 2 кодовых слова: $$(0000)^T$$ и $$(1111)^T$$. Считается, что слово передано с ошибкой, если не все разряды в нем одинаковы. Исправление одной ошибки производится по принципу голосования. Если в полученном слове больше единичных разрядов, то, очевидно, оно ближе к кодовому слову $$(1111)^T$$, чем к кодовому слову $$(0000)^T$$, поэтому декодирование производится в слово $$(1111)^T$$. По аналогичной причине, когда в принятом слове больше нулевых разрядов, декодирование производится в слово $$(0000)^T$$.
Путь $$Н$$- матрица размера $$ (п-к) \times п$$ и ранга $$(п-к)$$ над полем $$GF(2)$$. Эта матрица задает линейное отображение $$B^n \stackel{H} B^{n-k}$$ пространства $$В^n$$ в пространство $$В^{n-k}$$ по формуле $$у=Нх$$. Ядро этого линейного отображения или множество решений уравнения $$Hх=0$$, образующее подпространство пространства $$В^n$$, является
Отображение $$В^n\stackel{H} B^{n-k}$$ является отображением на все пространство $$B^{n-k}$$. Для систематической матрицы H это практически очевидно. Действительно, для любого $$yB^{n-k}$$ можно найти (построить) $$xB^n$$, такой, что $$y=Hx$$.
(рис 7.8) Разбиение пространства Bn на классы равнообразности
Произведение $$Hx, x \in B^n$$ называется синдромом [29], [33]. Фактически, синдромом вектора $$x\in B^n$$ является образ этого вектора при отображении -$$В^n \stackrel{H} B^{n-k}$$. Все векторы $$x \in B^n$$, имеющие один синдром, образуют класс. Так как синдром $$s = Hx \in B^{n-k}$$ имеет размерность $$n-k$$, всего существует $$2^{n-k}$$ классов (если проверочная матрица имеет ранг $$n-k$$, в частности, если матрица $$H$$ имеет систематический вид). Из определения линейного кода следует, что класс, которому соответствует нулевой синдром, является кодом $$C$$. Каждый класс $$C_i$$, отличный от кода, порождается "сдвигом" $$C_i =C+a_i$$ кода $$C$$ на один из векторов $$a_i$$ класса $$C_i$$. Действительно, если $$y \in C_i$$ ., то есть $$Hy = s_i, Ha_i =s_i$$, тогда $$H(y-a_i)=0$$ и, следовательно, $$y-a_i =c \in C$$ и $$y=a_i+c$$, где $$c \in C$$ - кодовое слово. Таким образом, любой некодовый вектор, имеющий синдром $$s \ne 0$$, можно представить в виде суммы кодового вектора и вектора, имеющего синдром $$s$$. Представление такого вида не является единственным. Некодовый вектор $$a_i$$ в этой сумме можно рассматривать как вектор ошибок, произошедших в тех разрядах кодового слова $$c$$, в которых соответствующие компоненты вектора $$a_i$$ равны 1. Из всех векторов ошибок, имеющих один синдром, наиболее вероятным является вектор $$l_s$$ (векторы) с минимальным весом (числом единичных компонент). Такой вектор (векторы) называется лидером класса.
Алгоритм декодирования заключается в следующем. Если получен вектор $$у$$ и $$Ну = s \ne 0$$, считаем, что ошибкам соответствует наиболее вероятный вектор из класса $$C_s$$, то есть лидер $$l_s$$ класса $$C_s$$. Тогда декодирование осуществляется в вектор $$z=у-l_s=У+l_s$$, получающийся из принятого вектора удалением лидера.
Рассмотрим пример построения кода по заданной проверочной матрице и декодирования полученного сообщения по синдрому. Пусть дана проверочная матрица $$H=\begin{pmatrix}1110\\ 1001\end{pmatrix}$$. Запишем уравнение для определения кодовых векторов (слов) для данной матрицы:
$$\begin{cases}x_1+x_2+x_3=0\\x_1+x_4=0\end{cases}\Rightarrow \begin{matrix}x_3=x_1+x_2\\x_4=x_1\end{matrix}$$$$x_1$$ и $$x_2$$ которые можно рассматривать как информационные разряды, задаются произвольно (всего 4 варианта 00, 01, 10, 11), а проверочные разряды $$x_3$$ и $$x_4$$ определяются через $$x_1$$ и $$x_2$$. В итоге все кодовые слова определяются из выражения
$$\begin{pmatrix}x_1\\x_2\\x_3\\x_4\end{pmatrix}=\begin{pmatrix}10\\01\\11\\10\end{pmatrix}*{x_1 \choose x_2},$$где $$x_1$$ и $$х_2$$ - информационные разряды, а $$\begin{pmatrix}10\\01\\11\\10\end{pmatrix}$$ - порождающая матрица, столбцами которой являются кодовые векторы.
Кодовые слова, рассматриваемые как векторы-столбцы, образуют матрицу кода
$$C=\begin{pmatrix}0011\\ 0101\\ 0110\\ 0011\end{pmatrix}$$Расстояние кода $$\rho_C$$ равно минимальному весу ненулевого слова $$\rho_C =2$$.
Найдем смежные классы, которые состоят из векторов пространства $$В^4$$, имеющих одинаковый синдром, и выберем в каждом классе лидера (вектор из класса с минимальным весом).
Синдромом является любое возможное значение произведения $$Н*х$$.
В данном случае имеется 4 синдрома: $${0 \choose 0}, {0 \choose 1}, {1 \choose 0}, {1 \choose 1}$$.Каждому синдрому соответствует смежный класс, синдром $${0 \choose 0}$$ соответствует коду. Смежные классы (столбцы матриц) для каждого синдрома и выбранные лидеры приведены в таблице.
| Синдром | $${o \choose 0}$$ | $${0 \choose 1}$$ | $${1 \choose 0}$$ | $${1 \choose 1}$$ |
| Класс смежности | $$\begin{pmatrix}0011\\0101\\0110\\0011\end{pmatrix}$$ | $$\begin{pmatrix}0011\\0101\\0110\\1100\end{pmatrix}$$ | $$\begin{pmatrix}0011\\1010\\0110\\0011\end{pmatrix}$$ | $$\begin{pmatrix}1100\\0101\\0110\\0011\end{pmatrix}$$ |
| Лидер | $$\begin{pmatrix}0\\0\\0\\0\end{pmatrix}$$ | $$\begin{pmatrix}0\\0\\0\\1\end{pmatrix}$$ | $$\begin{pmatrix}0\\1\\0\\0\end{pmatrix}$$ | $$\begin{pmatrix}1\\0\\0\\0\end{pmatrix}$$ |
В третьем смежном классе - два потенциальных лидера с весом (нормой), равным 1. Один из них выбирается в качестве лидера произвольно.
Рассмотрим на этом примере процесс декодирования полученного вектора (слова) с использованием синдромов. Пусть передавался кодовый вектор $$\begin{pmatrix}0\\1\\1\\0\end{pmatrix}$$ и в процессе переачи произошла ошибка в первом разряде. Это означает, что на приемном конце был получен вектор $$у=\begin{pmatrix}1\\1\\1\\0\end{pmatrix}=\begin{pmatrix}0\\1\\1\\0\end{pmatrix}+\begin{pmatrix}1\\0\\0\\1\end{pmatrix}$$, полученный из переданного вектора $$\begin{pmatrix}0\\1\\1\\0\end{pmatrix}$$ в результате добавления вектора ошибки $$\begin{pmatrix}1\\0\\0\\0\end{pmatrix}$$ (ошибка в первом разряде). Определим синдром, вычислив произведение $$Н*y$$. В данном случае получим $$H*y={1 \choose 1}$$. Это означает, что полученный вектор $$у$$ водит в четвертый смежный класс (см. таблицу). Лидером этого смежного класса является вектор $$l=\begin{pmatrix}1\\0\\0\\0\end{pmatrix}$$, соответствующий данному синдрому. Вычитая (добавляя) лидер к принятому вектору, производим декодирование $$y-l=y+l=\begin{pmatrix}0\\1\\1\\0\end{pmatrix}$$ В данном случае декодирование выполнено правильно.
Обработка информации в вычислительных системах невозможна без передачи сообщений между отдельными элементами (оперативной памятью и процессором, процессором и внешними устройствами). Примеры процессов передачи данных приведены в следующей таблице.
| Передатчик | Канал | Приемник | |
|---|---|---|---|
| Разговор людей | Голосовой аппарат человека | Воздушная среда. Акустические колебания | Слуховой аппарат человека |
| Телефонный разговор | Микрофон | Проводник. Переменный электрический ток | Динамик |
| Передача данных в сети Интернет | Модулятор | Проводник. |
Демодулятор |
| Радиотелефон, рация | Радиопередатчик | Эфир. Электромагнитные волны | Радиоприемник |
В перечисленных выше процессах передачи можно усмотреть определенное сходство. Общая схема передачи информации [31], [33], [32] показана на рис.7.1.
В канале сигнал подвергается различным воздействиям, которые мешают процессу передачи. Воздействия могут быть непреднамеренными (вызванными естественными причинами) или специально организованными (созданными) с какой-то целью некоторым противником. Непреднамеренными воздействиями на процесс передачи (помехами) могут являться уличный шум, электрические разряды (в т. ч. молнии), магнитные возмущения (магнитные бури), туманы, взвеси (для оптических линий связи) и т.п.
(рис 7.1) Общая схема передачи информации
Для изучения механизма воздействия помех на процесс передачи данных и способов защиты от них необходима некоторая модель. Процесс возникновения ошибок описывает модель под названием двоичный симметричный канал (ДСК) [32], [33], схема которой показана на рис.7.2.
(рис 7.2) Схема двоичного симметричного канала
При передаче сообщения по ДСК в каждом бите сообщения с вероятностью $$p$$ может произойти ошибка, независимо от наличия ошибок в других битах. Ошибка заключается в замене знака 0 на 1 или 1 на 0.
Некоторые типы ошибок:
Чаще других встречается замена знака. Этот тип ошибок исследован наиболее полно.
Если при кодировании сообщений используются оптимальные коды, то при появлении всего лишь одной ошибки все сообщение или его значительная часть может быть искажена. Рассмотрим пример. Пусть кодирование элементарных сообщений $$a_2a_3a_5a_1a_4$$ источника осуществляется с использованием кодовой таблицы
| Сообщения | Кодовое слово |
|---|---|
| $$a_1$$ | 00 |
| $$a_2$$ | 01 |
| $$a_3$$ | 10 |
| $$a_4$$ | 110 |
| $$a_5$$ | 111 |
Тогда закодированное сообщение имеет вид 011011100110. Если в первом знаке произойдет ошибка, то будет принято сообщение 111011100110, которое декодируется в слово $$a_5a_2a_4a_2a_3$$. Полное искажение сообщения из-за одной ошибки происходит вследствие того, что одно кодовое слово переходит в другое кодовое слово в результате замены одного или нескольких знаков. Пример показывает, что оптимальное кодирование плохо защищает сообщения от воздействия ошибок.
На практике необходим компромисс между экономностью кода и защитой от ошибок.
Сначала удаляется "бесполезная" избыточность (в основном статистическая), а затем добавляется "полезная" избыточность, которая помогает обнаруживать и исправлять ошибки.
Рассмотрим некоторые методы повышения надежности передачи данных. Широко известными методами борьбы с помехами являются следующие [34]:
Рассмотрим подробней каждый из этих способов.
Общим во всех этих способах повышения надежности является введение избыточности, то есть увеличение тем или иным способом объема передаваемого сообщения для возможности его правильной расшифровки при наличии искажений.
Следует отметить, что введение избыточности уменьшает скорость передачи информации, так как только часть передаваемого сообщения представляет интерес для получателя, а избыточная его доля введена для предохранения от шума и не несет в себе полезной информации.
Естественно выбирать такие формы введения избыточности, которые позволяют при минимальном увеличении объема сообщения обеспечивать максимальную помехоустойчивость.
Способы введения избыточности, позволяющие обнаруживать и исправлять ошибки, можно разделить на два класса, один из которых соответствует блоковым кодам, а другой - сверточным кодам [33]. Обе схемы кодирования применяются на практике. При блоковом кодировании последовательность, составленная из полученных в результате коди-рования источника кодовых слов, разбивается на блоки одинаковой длины. Каждый блок перед отправкой в канал обрабатывается независимо от других. Выход устройства, выполняющего сверточное кодирование, напротив, зависит не только от обрабатываемых в данный момент знаков, но и от предыдущих знаков. Остановимся более подробно на блоковом кодировании.
Как было показано ранее, ошибка в одном лишь разряде может испортить все сообщение. Чтобы избежать таких тяжелых последствий, сообщения, закодированные каким-либо экономным кодом, перед направлением в канал делятся на блоки одинаковой длины и каждый блок передается отдельно. При этом методы, позволяющие обнаруживать и исправлять ошибки, применяются к каждому блоку. Такой прием напоминает разделение большого судна на несколько изолированных друг от друга отсеков, что позволяет при пробоине в одном отсеке сохранить судно и груз в других отсеках.
Рассмотрим схему передачи данных, показанную на рис.7.3.
С кодирующего устройства в канал поступают закодированные блоки (кодовые слова) одинаковой длины $$n$$. В канале в результате действия различных помех в некоторых битах передаваемого сообщения могут происходить ошибки. Процедуру кодирования при передаче и
(рис 7.3) Схема передачи данных
декодирования при приеме с использованием одной и той же кодовой таблицы иллюстрируем рис.7.4. Предполагается, что появление ошибок описывается моделью дискретного симметричного канала
(рис 7.4) Использование кодовой таблицы для кодирования и декодирования
В геометрической интерпретации эти блоки можно рассматривать как точки n-мерного пространства $$B^n$$, где $$B=\{0, 1\}$$. Точки этого пространства представляют собой последовательности чисел 0 и 1 длины $$n$$. Пространства $$B^n$$ для $$n = 1, 2, 3$$ можно представить в виде угловых точек единичного интервала ($$n=1$$), вершин квадрата со стороной, равной 1 ($$n=2$$), и вершин куба с ребрами длины 1 ($$n=3$$). Эти пространства условно изображены на рис.7.5.
Код, используемый для обнаружения и исправления ошибок, представляет собой некоторое подмножество пространства $$B^n$$. В качестве примера можно привести код $$с=\{000\; 110\; 101\; 011\}\subset B^3$$. Кодовые слова этого кода как точки пространства $$B3$$ изображены на рис. 7.6 белыми кружками. Если представить куб расположенным в трехмерном пространстве, то словам данного кода соответствуют вершины тетраэдра. Более полезным
(рис 7.5) Геометрическое представление пространства Bn для n = 1, 2 и 3
с практической точки зрения является то, что каждое слово кода содержит четное число единиц. Если при передаче кодового слова через канал произойдет одна ошибка, то число единиц в слове станет нечетным. Проверяя свойство четности числа единиц в слове после получения его из канала на приемном конце, можно обнаружить одну ошибку. В данном случае для кодирования четырех знаков используется 3 двоичных разряда, хотя достаточно двух. Однако благодаря такой избыточности удается обнаружить одну ошибку.
(рис 7.6) Код в B3, обнаруживающий одну ошибку
В соответствии с общей схемой передачи сообщений в кодирующем и декодирующем устройствах используется одна и та же кодовая таблица и, следовательно, множество кодовых слов. При передаче кодового слова через канал возможны следующие ситуации.
Передавалось и было получено некоторое кодовое слово $$c_i$$. Эта ситуация, которая показана в верхней части рис.7.7, соответствует отсутствию ошибок при передаче.
Передавалось кодовое слово ci, а получено было сообщение, которое не является кодовым словом. При попытке декодировать это сообщение будет обнаружено, что такого слова в кодовой таблице нет. Это означает, что ошибка, произошедшая при передаче и исказившая кодовое слово, обнаружена. Эта ситуация изображена в средней части рис.7.7.
(рис 7.7) Возможные варианты передачи кодового слова через канал
В процессе передачи кодовое слово $$с_i$$ может так исказиться из-за ошибок, что оно превратится в другое кодовое слово $$с_j$$. В этом случае ошибка не обнаруживается, поскольку полученное сообщение также является кодовым словом, и декодирование будет выполнено неверно. Такая ситуация показана в нижней части рис.7.7.
Определение. Код обнаруживает $$t$$ ошибок, если $$\forall \; r \le t\; r$$ ошибок в кодовом слове переводит его в слово, которое не входит в код.
Код "Тетраэдр" из предыдущего примера обнаруживает одну ошибку (меняется четность), но не обнаруживает две ошибки. Например, слово 101 в результате двух ошибок в первых двух знаках переходит в другое кодовое слово (реализуется третий вариант передачи на рис.7.7). Легко заметить, что данный код обнаруживает 3 ошибки, 5 ошибок и вообще любое нечетное число ошибок, но не обнаруживает любое четное число ошибок. Поэтому, в соответствии с приведенным определением, этот код не обнаруживает 3 или 5 ошибок, а только одну.
В пространстве $$B^n$$ вводится мера отличия двух точек этого пространства, которая называется расстоянием Хеминга [29], [33], [34].
Определение. Расстоянием $$\rho(\alpha, \beta)$$, по Хемингу, между вершинами $$\alpha=\alpha_1\alpha_2 \dots \alpha_n \in B^n$$ и $$\beta=\beta_1 \beta_2 \dots \beta_n \in B^n$$ называется число разрядов, в которых эти вершины различаются.
В виде математической формулы это можно записывать так:
$$\rho(\alpha, \beta)=\sum_{i=1}^{n}|\alpha_i-\beta_i|$$где через $$|x|$$ обозначается
В качестве примера рассмотрим расстояние Хеминга между двумя точками (последовательностями или словами) $$\alpha=0110101$$ и $$\beta=1111001$$ пространства $$B^7$$. Эти последовательности отличаются в первой, четвертой и пятой позициях, следовательно, $$\rho(\alpha, \beta)=3$$.
Вещественную функцию $$d(x,y)$$ двух переменных на множестве $$V$$ принято называть расстоянием, если она обладает следующими свойствами:
$$d(x,y) \ge 0 \forall x, y \in V, d(x,y) =0 \mbox{\ тогда\ и\ только\ тогда,\ когда\ } x=y;\\ d(x,y) = d(y,x);\\ d(x,z) \le d(x,y) + d(y,z) (\mbox{неравенство треугольника}).$$Расстояние Хеминга обладает перечисленными выше свойствами. Два первых свойства очевидным образом следуют из определения расстояния Хеминга (или из приведенной выше формулы для расстояния Хеминга), а третье свойство вытекает из следующей последовательности равенств и неравенств
$$\rho(\alpha, \beta)=\sum_{i=1}^{n}|\alpha_i-\beta_i|=\sum_{i=1}^{n}|\alpha_i-\gamma_i+\gamma_i-\beta_i|\le \sum_{i=1}^{n}(|\alpha_i-\gamma_i|+|\gamma_i-\beta_i|)=\\ =\sum_{i=1}^{n}|\alpha_i-\gamma_i|+\sum_{i=1}^{n}|\gamma_i-\beta_i|=\rho(\alpha, \gamma)+\rho(\gamma, \beta)$$Возможности обнаруживать и исправлять ошибки с помощью кода C зависят от его характеристики, которая называется кодовым расстоянием [34].
Определение. Кодовым расстоянием $$т_C$$ кода $$C$$ называется минимальное расстояние между различными кодовыми словами (векторами).
$$\rho_c min_{\substack{\alpha, \beta \in C\\ \alpha \ne \beta}}\rho(\alpha, \beta)$$С использованием расстояния Хеминга в пространстве $$B^n$$ можно определить аналоги таких геометрических понятий, как сфера и шар [34]. Эти понятия потребуются в дальнейшем для объяснения принципов обнаружения и исправления ошибок с помощью кодов.
Сферой радиуса $$t$$ с центром в точке $$\alpha$$ является множество
$$S_{\alpha}^0=\{\beta \in B^n|\rho(\alpha, \beta)=t\}$$Число точек $$|S_{\alpha}^0(t)|$$ в сфере $$S_{\alpha}^0(t) $$ определяется выражением
$$|S_{\alpha}^0(t)|={n\choose t}=C_n^1$$Шаром радиуса $$t$$ с центром в точке $$\alpha$$ называется множество
$$S_{\alpha}(t)=\{\beta \in B^n|\rho (\alpha, \beta) \le t\}$$Число точек $$|S_{\alpha}(t)|$$ в шаре $$S_{\alpha}(t)$$ определяется выражением
$$|S_{\alpha}(t)|=1+{n\choose 1}+{n \choose 2}+\dots+{n\choose 1}$$Замечание. Если имеется некоторое исходное слово $$\alpha$$, а слово $$\beta$$ получилось из $$\alpha$$ в результате одной ошибки, произошедшей, например, при передаче слова $$\alpha$$ по каналу, то $$\rho(\alpha, \beta)=1$$, т. е. в смысле Хеминга расстояние между ними равно 1.
Аналогичным образом, если при передаче слова $$\alpha$$ произошло $$\kappa$$ ошибок и оно превратилось в слово $$\beta$$ то $$\rho(\alpha,\betar)=\kappa$$.
Утверждение. Код обнаруживает $$\tau$$ ошибок, если для любых кодовых слов $$\alpha$$ и $$\beta$$ $$(\forall \alpha, \beta \in C) \rho(\alpha, \beta) \ge t+1$$ или $$\rho_c \ge t+1$$.
Рассмотрим, как происходит декодирование сообщения после его передачи через канал. Если при передаче не произошло ошибок, то будет получено кодовое слово. Естественно считать это кодовое слово результатом декодирования.
Если в результате передачи получено не кодовое слово, то произошла ошибка. В этом случае целесообразно использовать декодирование в ближайшее кодовое слово. Такой подход имеет объяснение. Действительно, пусть полученное слово $$\delta$$ ближе к кодовому слову $$\alpha$$, чем к любому другому кодовому слову, т. е. $$\rho(\alpha, \delta) < \rho(\beta, \delta)$$ для всех кодовых слов $$b\ne a$$. Если сравнить различные гипотезы о том, какое исходное слово было пе-редано, то гипотеза о передаче слова $$\alpha$$ при условии получения слова $$\delta$$ является наиболее вероятной. Это следует из того, что первая гипотеза (основная) соответствует меньшему числу ошибок при передаче, чем конкурирующие гипотезы.
Утверждение. Код исправляет $$t$$ ошибок, если для любых кодовых слов $$\alpha$$ и $$\beta (\forall \alpha, \beta \in C) \rho(\alpha, \beta) \ge 2t+1$$ или $$\rho_c \ge 2t+1$$.
Для доказательства рассмотрим шары радиуса $$t$$ с центрами в кодовых словах. Из неравенства треугольника для расстояния Хеминга следует, что эти шары не пересекаются. Тогда при передаче любого кодового слова и при числе ошибок, не превышающем $$t$$, полученное слово будет находиться в шаре с центром в передаваемом слове и декодироваться (по методу декодирования в ближайшее кодовое слово) в переданное слово.
Из последних двух утверждений следует, что важнейшей характеристикой кода, определяющей его корректирующие возможности, является его кодовое расстояние.
Рассмотрим, следуя [34], какие задачи требуется решать при создании кодов, с помощью которых можно эффективно обнаруживать и исправлять ошибки, возникающие при передаче сообщений. Одна из важнейших задач теории кодирования состоит в следующем. Требуется построить код, исправляющий $$t$$ ошибок и имеющий максимально возможное число точек. В геометрической постановке эта же задача звучит следующим образом: среди вершин единичного $$n$$-мерного куба $$B^n$$ требуется выделить максимальное число таким способом, чтобы расстояние между любыми двумя
Другая, связанная с предыдущей, задача состоит в расположении $$s$$ точек в вершинах $$B^n$$ так, чтобы наименьшее из попарных расстояний между ними было возможно большим. Это расстояние обозначается через $$d(s, n)$$.
Выражения "построить", "выделить", "расположить" нуждаются в уточнении, так как нам вовсе не безразлично, в каком виде будет задан искомый код. Самый простой способ - перечисление всех кодовых точек - является неэффективным, требует большой памяти. Поэтому нужен такой способ задания кода, который позволяет просто восстановить каждую точку кода по ее номеру. Другими словами, код должен иметь простую реализацию. С некоторыми просто реализуемыми кодами мы познакомимся ниже. С другой стороны, мы хотим иметь возможность просто восстанавливать исходное сообщение на выходе.
Таким образом, "хороший код" должен удовлетворять следующим трем естественным требованиям:
Следует отметить, что эти требования в значительной степени являются противоречивыми, так как код $$c$$, исправляющий много ошибок, вовсе не обязан иметь простую реализацию и тем более простой алгоритм декодирования. Поэтому на практике применяются коды, которые обладают в достаточной мере всеми тремя перечисленными выше качествами.
$$A(n,s)$$ - максимальное число точек кода в $$B^n$$, расстояние между любыми двумя кодовыми словами не меньше $$s$$.
Для количественной оценки свойств кода полезно знать, насколько его параметры отличаются от параметров "идеального" кода. Для этого необходимо иметь хотя бы приближенные значения важнейших параметров "идеального" кода, т. е. значения $$A(n, 2t+1)$$ и $$d(s, n)$$. Следует отметить, что функции $$A(n, 2t+1)$$ и $$d(s, n)$$ не являются единственными параметрами, характеризующими качество кода. Не менее важными являются также такие параметры кода, как вероятность правильного декодирования и вероятность обнаружения ошибки. Имеется также еще ряд других важных критериев, применяющихся для оценки качества кодов.
Если расстояние между любыми двумя точками кода не меньше, чем $$2t+1$$, то шары радиуса $$t$$ с центрами в кодовых словах не пересекаются. Поэтому общее число точек в этих шарах равно: $$|V|*(1+C_n^1+C_n^2+\dots+C_n^t)$$, где $$|V|$$ - число точек (кодовых слов) в коде $$V$$, а $$ (1 + С_n^1 + С_n^2 +\dots + С_n^t)$$ число точек в шаре радиуса $$t$$. Так как число точек, попавших в шары, очевидно, не превосходит общего числа точек (двоичных слов) в $$B^n$$, то $$\V\*(1+C_n^1+C_n^2+\dots+C_n^t)\le 2^n$$. Это неравенство справедливо для любого множества с расстоянием между любыми двумя точками не меньше, чем $$2t+1$$, в том числе и для кода с максимальным числом слов $$A(n, 2t+1) $$, откуда и следует неравенство Хеминга.
$$A(n,2t+1) \le \frac{2^n}{(1+C_n^1+C_n^2+\dots+C_n^t)}$$Для максимального числа слов $$A(n, 2t+1) $$ в коде, исправляющем $$t$$ ошибок, может быть получена оценка снизу.
Утверждение (неравенство Варшамова - Гилберта):
$$\frac{2^n}{(1+C_n^1+C_n^2+\dots+C_n^{2t})}\le A(n,2t+1)$$Чтобы доказать неравенство Варшамова - Гилберта, можно рассмотреть следующую процедуру построения кода, исправляющего $$t$$ ошибок.
В качестве первого кодового слова возьмем произвольное слово (вектор) из $$B^n$$. Рассмотрим шар радиуса $$2t$$ с центром в данном слове. Если в $$B^n$$ есть слова, не вошедшие в этот шар, то в качестве второго кодового слова выберем любое из них. В качестве третьего кодового слова выберем любое слово, не вошедшее ни в один из построенных ранее шаров. Построим шар радиуса $$2t$$ с центром в данном слове. Продолжим эту процедуру выбора кодовых слов и построения шаров до тех пор, пока не будут исчерпаны все точки пространства $$B^n$$. Предположим, построение кода завершилось за $$m$$ шагов. После завершения этой процедуры пространство $$B^n$$ будет покрыто $$m$$ построенными шарами, содержащими по $$1+С_n^1+С_n^2+\dots+С_n^{2t}$$ точек каждый. Поскольку шары могут пересекаться, справедливо неравенство $$т*(1+С_n^1 + С_n^2 +\dots+С_n^{2t}) \ge 2^n$$. Центры шаров образуют код $$C$$, имеющий, как следует из способа построения, кодовое расстояние $$\rho_C \ge 2t+1$$. Из того, что $$A(n, 2t +1) $$- это максимально возможное число точек кода с кодовым расстоянием не меньше, чем $$2t+1$$, следует, что $$A(n, 2t+1)\ge m$$ и $$А(п, 2t+1)*(1+С_n^1+С_n^2+\dots+С_n^{2t})\ge 2^n$$ . Последнее неравенство эквивалентно неравенству Варшамова - Гилберта.
Одним из подходов к регулярному построению кодов является применение в качестве кодовых множеств линейных подпространств [29], [33], [34]. Одно из преимуществ такого подхода заключается в хорошо изученной структуре подпространств линейных векторных пространств.
Для построения кодов, обнаруживающих и исправляющих ошибки, используются векторные пространства над конечным полем $$GF(2)$$ [32]. В этом случае множество ($$n$$-мерный куб) $$B^n$$ рассматривается как линейное векторное пространство над конечным полем $$GF(2)$$. Точки из $$B^n$$ становятся векторами, их можно складывать и умножать на числа из поля $$GF(2)$$.
Специфика некоторых понятий линейной алгебры в векторном пространстве $$B^n$$ является следствием особенностей поля $$GF(2)$$. Сложение векторов из $$B^n$$ производится покоординатно с учетом особенностей операции сложения в поле $$GF(2)$$.
Сложение и умножение в поле определяется следующими таблицами.
| $$\oplus$$ | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| $$\times$$ | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 0 | 1 |
Сложение в поле $$GF(2) $$ (сложение по модулю 2) часто обозначается $$\oplus$$. Этим же знаком будем обозначать сложение векторов из $$B^n$$. Следует отметить справедливое для всех векторов $$\alpha \in B^n$$ равенство $$\alpha \oplus \alpha = 0$$, вытекающее из таблицы сложения. Оно означает, что любой вектор является противоположным себе $$\alpha =-\alpha$$, а также что при заданных $$\alpha$$ и ($$\beta$$ уравнение имеет решение $$\chi = \alpha \oplus \beta= \beta \oplus \alpha$$.
Рассмотрим особенности еще некоторых понятий линейной алгебры.
Линейная комбинация в $$B^n$$. Учитывая, что $$B^n$$ рассматривается как векторное пространство над конечным полем $$GF(2)$$, содержащим только два элемента 0 и 1,
Линейная оболочка множества векторов из $$B^n \; v_{j_1}, v_{j_2}, \dots, v_{j_k}$$ - это совокупность различных сумм этих векторов. Линейная оболочка векторов $$\alpha, \beta, \dots, \gamma$$ будет обозначаться через $$ [\alpha, \beta, \dots, \gamma]$$.
Линейная зависимость векторов из $$B^n$$. Векторы $$v_{j_1}, v_{j_2}, \dots, v_{j_k}$$линейно зависимы, если существует сумма некоторых из них, равная 0.
Векторы $$v_{j_1}, v_{j_2}, \dots, v_{j_k}$$линейно независимы, если любая сумма некоторых из них не равна 0.
Утверждение. Если векторы $$v_{j_1}, v_{j_2}, \dots, v_{j_k}$$ независимы, то все их линейные комбинации (суммы) различны.
Доказательство. Предположим, что $$v_{j_1}, v_{j_2}, \dots, v_{j_k}=v_{j_1}, v_{j_2}, \dots, v_{j_m}$$ Удалив из левой и правой частей этого равенства одинаковые векторы и перенеся оставшиеся из правой части в левую, получим нулевую сумму векторов. Это противоречит их линейной независимости.
Всего из $$m$$ линейно независимых векторов можно составить
$$1+m+{m \choose 2}+\dots+{m \choose m}=2^m$$линейных комбинаций, и все они различны.
Из доказанного утверждения следует, что линейная оболочка $$m$$ линейно независимых векторов содержит $$2^m$$ вектора.
Рассмотрим пример. Пусть имеем два вектора
$$\alpha_1=\begin{pmatrix}1\\0\\0\end{pmatrix},\; \alpha_2=\begin{pmatrix}1\\1\\1\end{pmatrix}$$ $$\alpha_1=\begin{pmatrix}1\\0\\0\end{pmatrix},\; \alpha_2=\begin{pmatrix}1\\1\\1\end{pmatrix}\; \alpha_3=\begin{pmatrix}0\\1\\1\end{pmatrix},\; \alpha_4=\begin{pmatrix}0\\0\\0\end{pmatrix}$$Их линейная оболочка $$[\alpha_1, \alpha_2]$$ состоит из четырех векторов На традиционном изображении $$B^3$$ в виде точек куба $$\alpha_1, \alpha_2, \alpha_3, \alpha_4$$ образуют плоскость (увеличенные светлые вершины куба на рисунке).
(рис )
Подпространства в $$B^n$$. Подпространством векторного пространства $$B^n$$ называется подмножество векторов из $$B^n$$, замкнутое относительно операций сложения и умножения на число из поля $$GF(2)$$. Линейная оболочка $$[\alpha, \beta, \dots \gamma]$$ векторов $$\alpha, \beta, \dots, \gamma$$ уявляется подпространством пространства $$B^n$$.
Например, рассмотренная в предыдущем примере линейная оболочка из четырех векторов является подпространством, а множество векторов
$$\beta_1=\begin{pmatrix}1\\0\\0\end{pmatrix},\; \beta_2=\begin{pmatrix}1\\1\\1\end{pmatrix}\; \beta_3=\begin{pmatrix}0\\0\\1\end{pmatrix},\; \beta_4=\begin{pmatrix}0\\0\\0\end{pmatrix}$$подпространством не является, поскольку оно не замкнуто относительно операции сложения. Например, $$\beta_1+\beta_2$$ не входит в это множество векторов.
По аналогии с подпространствами в $$R^n$$ подпространства в $$B^n$$ могут задаваться
Нормой вектора $$\alpha \in B^n$$ называется число $$||\alpha||$$ единичных координат этого вектора. В кодировании
Кодовое расстояние линейного кода может быть вычислено проще, чем кодовое расстояние произвольного кода. Учитывая, что для слов $$\alpha \in C, \beta \in C$$ линейного кода $$C$$ справедливо $$\alpha \oplus \beta \in C$$, выполняется следующая цепочка равенств
$$р_с =min_{\alpha \ne \beta}\rho (\alpha, \beta) = min_{\alpha \ne \beta}||\alpha \oplus \beta||=min_{\gamma \in C}||\gamma||$$Определение. Пусть $$H$$ - матрица над полем $$GF(2)$$ размера $$ (n-k)\times n$$ и ранга $$(n-k)$$. Множество $$C \subset GF^n(2)$$ решений уравнения $$Hx=0$$ называется линейным $$(n,k)$$ кодом. $$H$$ - проверочная матрица, $$n$$ - длина кода, $$k$$ - размерность кода. Если матрица $$H$$ имеет вид $$H=(A E_{n-k})$$, где $$E_{n-k}$$ -
Рассмотрим, как можно получить линейный код, зная порождающую матрицу. Для этого решим уравнение $$Hx=0$$ и найдем кодовые слова. В матричном виде уравнение для кодовых слов запишется в виде
$$Hx=n-k\{(\overbrace{A}^{k} \overbrace{E_{n-k}}^{n-k})*\begin{pmatrix}x_1\\\vdots\\x_k\\x_{k+1}\\\vdots\\x_n\end{pmatrix}=A*\begin{pmatrix}x_1\\x_2\\\vdots\\x_k\end{pmatrix}+E_{n-k}*\begin{pmatrix}x_{k+1}\\x_{k+2}\\\vdots\\x_n\end{pmatrix}=A*\begin{pmatrix}x_1\\x_2\\\vdots\\x_k\end{pmatrix}+\begin{pmatrix}x_{k+1}\\x_{k+2}\\\vdots\\x_n\end{pmatrix}=0\\ \begin{pmatrix}x_{k+1}\\x_{k+2}\\\vdots\\x_n\end{pmatrix}=-A*\begin{pmatrix}x_1\\x_2\\\vdots\\x_k\end{pmatrix}$$Чтобы найти решение, нужно произвольно задать $$k$$ компонент $$x_1= u_1, x_2=u_2,\dots , x_k = u_k$$ вектора $$x$$, а остальные вычислить по формуле (2.6). Таким образом, первые $$k$$ компонент вектора $$x$$ полностью его определяют
$$\begin{pmatrix}u_1\\u_2\\\vdots\\u_k\\x_{k+1}\\x_{k+2}\\\vdots\\x_n\end{pmatrix}={E_k \choose -A}*\begin{pmatrix}u_1\\u_2\\\vdots\\u_k\end{pmatrix}$$Матрица $$G={E_k \choose -A}$$ называется порождающей. Ее столбцы образуют базис пространства решений системы $$Hx=0$$. Учитывая особенности поля $$GF(2)$$, порождающая матрица имеет вид $$G ={E_k \choose A}$$.
Нетрудно показать, что справедливо равенство $$H *G=O$$, где $$O$$ - матрица из нулевых элементов, имеющая $$n-k$$ строк и $$k$$ столбцов.
Для того чтобы лучше понять свойства
Свойства
Лемма. Линейный код $$C$$ с проверочной матрицей $$H_C$$ имеет кодовое расстояние $$\rho_{C_s} \ge s +1$$ тогда и только тогда, когда любые s столбцов матрицы $$H_C$$ линейного кода $$C$$ линейно независимы.
Если любые $$s$$ столбцов матрицы $$H_C$$ линейно независимы, то никакой вектор $$x=(x_1, x_2, \dots, x_n)^T$$, имеющий $$s$$ или менее ненулевых (единичных) компонент, не обращает в ноль произведение $$H_c * x =h_1x_1+h_2x_2+\dots h_nx_n$$. Это означает, что нормы всех кодовых слов, то есть слов $$z$$, для которых справедливо $$H_C*z=0$$, больше $$s$$, и следовательно, кодовое расстояние $$\rho_C \ge s+1$$.
Пусть теперь линейный код $$C$$ с проверочной матрицей $$H_C$$ имеет кодовое расстояние $$\rho_C \ge s+1$$. Для доказательства линейной независимости любых $$s$$ столбцов проверочной матрицы $$H_C$$ предположим противное, то есть предположим, что существует $$t<s$$ линейно зависимых столбцов матрицы $$H_C$$ Это значит, что сумма $$h_{i_1}+h_{i_2}+ \dots h_{i_k}k \le t < s$$ некоторых из этих столбцов равна нулевому вектору пространства $$B^n$$. Эту сумму можно представить как произведение $$h_{i_1}+h_{i_2} +\dots h_{i_k}, =H_c*x$$, где $$x$$ - вектор, у которого компоненты с номерами $$i_1, i_2, \dots, i_k, k \le t < s$$ равны 1, а остальные компоненты равны 0. Значит $$x$$ - кодовый вектор с нормой $$k<s$$, что противоречит тому, что кодовое расстояние $$\rho_C \ge s+1$$.
Рассмотрим некоторые примеры
Код с разрядом для проверки на четность является
или
$$х_4=х_1+х_2+х_3, $$то есть четвертый разряд (проверочный), равный сумме трех информационных, делает сумму всех разрядов кодового слова четной. Каждый столбец проверочной матрицы линейно независим, поэтому из доказанной выше леммы следует, что код имеет кодовое расстояние, равное 2, и следовательно, обнаруживает одну ошибку. Ошибка обнаруживается, если число единичных разрядов в принятом слове нечетно (сумма всех разрядов принятого слова по модулю 2 не равна 0). В этом коде 8 кодовых слов.
Код с повторением является
Линейное уравнение, определяющее код, в данном случае имеет вид
$$\begin{cases}\begin{matrix} x_1+x_2=0\\ x_1+x_3=0\\ x_1+x_4=0 \end{matrix} \end{cases}$$а его решения описываются соотношениями $$х_2=х_1,х_3=х_1,х_4=х_1$$. Эти равенства означают, что три проверочных разряда повторяют один информационный разряд. Любые 3 столбца проверочной матрицы являются линейно независимыми (сумма любых трех столбцов не равна нулевому столбцу), поэтому кодовое расстояние, равное 4, обеспечивает исправление одной ошибки и обнаружение трех. Код содержит всего 2 кодовых слова: $$(0000)^T$$ и $$(1111)^T$$. Считается, что слово передано с ошибкой, если не все разряды в нем одинаковы. Исправление одной ошибки производится по принципу голосования. Если в полученном слове больше единичных разрядов, то, очевидно, оно ближе к кодовому слову $$(1111)^T$$, чем к кодовому слову $$(0000)^T$$, поэтому декодирование производится в слово $$(1111)^T$$. По аналогичной причине, когда в принятом слове больше нулевых разрядов, декодирование производится в слово $$(0000)^T$$.
Путь $$Н$$- матрица размера $$ (п-к) \times п$$ и ранга $$(п-к)$$ над полем $$GF(2)$$. Эта матрица задает линейное отображение $$B^n \stackel{H} B^{n-k}$$ пространства $$В^n$$ в пространство $$В^{n-k}$$ по формуле $$у=Нх$$. Ядро этого линейного отображения или множество решений уравнения $$Hх=0$$, образующее подпространство пространства $$В^n$$, является
Отображение $$В^n\stackel{H} B^{n-k}$$ является отображением на все пространство $$B^{n-k}$$. Для систематической матрицы H это практически очевидно. Действительно, для любого $$yB^{n-k}$$ можно найти (построить) $$xB^n$$, такой, что $$y=Hx$$.
(рис 7.8) Разбиение пространства Bn на классы равнообразности
Произведение $$Hx, x \in B^n$$ называется синдромом [29], [33]. Фактически, синдромом вектора $$x\in B^n$$ является образ этого вектора при отображении -$$В^n \stackrel{H} B^{n-k}$$. Все векторы $$x \in B^n$$, имеющие один синдром, образуют класс. Так как синдром $$s = Hx \in B^{n-k}$$ имеет размерность $$n-k$$, всего существует $$2^{n-k}$$ классов (если проверочная матрица имеет ранг $$n-k$$, в частности, если матрица $$H$$ имеет систематический вид). Из определения линейного кода следует, что класс, которому соответствует нулевой синдром, является кодом $$C$$. Каждый класс $$C_i$$, отличный от кода, порождается "сдвигом" $$C_i =C+a_i$$ кода $$C$$ на один из векторов $$a_i$$ класса $$C_i$$. Действительно, если $$y \in C_i$$ ., то есть $$Hy = s_i, Ha_i =s_i$$, тогда $$H(y-a_i)=0$$ и, следовательно, $$y-a_i =c \in C$$ и $$y=a_i+c$$, где $$c \in C$$ - кодовое слово. Таким образом, любой некодовый вектор, имеющий синдром $$s \ne 0$$, можно представить в виде суммы кодового вектора и вектора, имеющего синдром $$s$$. Представление такого вида не является единственным. Некодовый вектор $$a_i$$ в этой сумме можно рассматривать как вектор ошибок, произошедших в тех разрядах кодового слова $$c$$, в которых соответствующие компоненты вектора $$a_i$$ равны 1. Из всех векторов ошибок, имеющих один синдром, наиболее вероятным является вектор $$l_s$$ (векторы) с минимальным весом (числом единичных компонент). Такой вектор (векторы) называется лидером класса.
Алгоритм декодирования заключается в следующем. Если получен вектор $$у$$ и $$Ну = s \ne 0$$, считаем, что ошибкам соответствует наиболее вероятный вектор из класса $$C_s$$, то есть лидер $$l_s$$ класса $$C_s$$. Тогда декодирование осуществляется в вектор $$z=у-l_s=У+l_s$$, получающийся из принятого вектора удалением лидера.
Рассмотрим пример построения кода по заданной проверочной матрице и декодирования полученного сообщения по синдрому. Пусть дана проверочная матрица $$H=\begin{pmatrix}1110\\ 1001\end{pmatrix}$$. Запишем уравнение для определения кодовых векторов (слов) для данной матрицы:
$$\begin{cases}x_1+x_2+x_3=0\\x_1+x_4=0\end{cases}\Rightarrow \begin{matrix}x_3=x_1+x_2\\x_4=x_1\end{matrix}$$$$x_1$$ и $$x_2$$ которые можно рассматривать как информационные разряды, задаются произвольно (всего 4 варианта 00, 01, 10, 11), а проверочные разряды $$x_3$$ и $$x_4$$ определяются через $$x_1$$ и $$x_2$$. В итоге все кодовые слова определяются из выражения
$$\begin{pmatrix}x_1\\x_2\\x_3\\x_4\end{pmatrix}=\begin{pmatrix}10\\01\\11\\10\end{pmatrix}*{x_1 \choose x_2},$$где $$x_1$$ и $$х_2$$ - информационные разряды, а $$\begin{pmatrix}10\\01\\11\\10\end{pmatrix}$$ - порождающая матрица, столбцами которой являются кодовые векторы.
Кодовые слова, рассматриваемые как векторы-столбцы, образуют матрицу кода
$$C=\begin{pmatrix}0011\\ 0101\\ 0110\\ 0011\end{pmatrix}$$Расстояние кода $$\rho_C$$ равно минимальному весу ненулевого слова $$\rho_C =2$$.
Найдем смежные классы, которые состоят из векторов пространства $$В^4$$, имеющих одинаковый синдром, и выберем в каждом классе лидера (вектор из класса с минимальным весом).
Синдромом является любое возможное значение произведения $$Н*х$$.
В данном случае имеется 4 синдрома: $${0 \choose 0}, {0 \choose 1}, {1 \choose 0}, {1 \choose 1}$$.Каждому синдрому соответствует смежный класс, синдром $${0 \choose 0}$$ соответствует коду. Смежные классы (столбцы матриц) для каждого синдрома и выбранные лидеры приведены в таблице.
| Синдром | $${o \choose 0}$$ | $${0 \choose 1}$$ | $${1 \choose 0}$$ | $${1 \choose 1}$$ |
| Класс смежности | $$\begin{pmatrix}0011\\0101\\0110\\0011\end{pmatrix}$$ | $$\begin{pmatrix}0011\\0101\\0110\\1100\end{pmatrix}$$ | $$\begin{pmatrix}0011\\1010\\0110\\0011\end{pmatrix}$$ | $$\begin{pmatrix}1100\\0101\\0110\\0011\end{pmatrix}$$ |
| Лидер | $$\begin{pmatrix}0\\0\\0\\0\end{pmatrix}$$ | $$\begin{pmatrix}0\\0\\0\\1\end{pmatrix}$$ | $$\begin{pmatrix}0\\1\\0\\0\end{pmatrix}$$ | $$\begin{pmatrix}1\\0\\0\\0\end{pmatrix}$$ |
В третьем смежном классе - два потенциальных лидера с весом (нормой), равным 1. Один из них выбирается в качестве лидера произвольно.
Рассмотрим на этом примере процесс декодирования полученного вектора (слова) с использованием синдромов. Пусть передавался кодовый вектор $$\begin{pmatrix}0\\1\\1\\0\end{pmatrix}$$ и в процессе переачи произошла ошибка в первом разряде. Это означает, что на приемном конце был получен вектор $$у=\begin{pmatrix}1\\1\\1\\0\end{pmatrix}=\begin{pmatrix}0\\1\\1\\0\end{pmatrix}+\begin{pmatrix}1\\0\\0\\1\end{pmatrix}$$, полученный из переданного вектора $$\begin{pmatrix}0\\1\\1\\0\end{pmatrix}$$ в результате добавления вектора ошибки $$\begin{pmatrix}1\\0\\0\\0\end{pmatrix}$$ (ошибка в первом разряде). Определим синдром, вычислив произведение $$Н*y$$. В данном случае получим $$H*y={1 \choose 1}$$. Это означает, что полученный вектор $$у$$ водит в четвертый смежный класс (см. таблицу). Лидером этого смежного класса является вектор $$l=\begin{pmatrix}1\\0\\0\\0\end{pmatrix}$$, соответствующий данному синдрому. Вычитая (добавляя) лидер к принятому вектору, производим декодирование $$y-l=y+l=\begin{pmatrix}0\\1\\1\\0\end{pmatrix}$$ В данном случае декодирование выполнено правильно.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.