Все векторы имеющие один синдром образуют

Декодирование линейного кода по синдрому

Путь — матрица размера (п-к) times п и ранга (п-к) над полем GF(2) . Эта матрица задает линейное отображение $B^n stackel{H} B^{n-k}$ пространства В^n в пространство $В^{n-k}$ по формуле у=Нх . Ядро этого линейного отображения или множество решений уравнения Hх=0 , образующее подпространство пространства В^n , является линейным кодом. Можно рассмотреть разбиение пространства B^n на классы равнообразности. В один класс входят все элементы B^n , которые при отображении $В^n stackel{H} B^{n-k}$ переходят в один и тот же элемент пространства $B^{n-k}$ . Элемент пространства $B^{n-k}$ , в который переходят все элементы одного класса, называется синдромом. Pис.7.8 иллюстрирует разбиение пространства B^n на классы равнообразности.

Отображение $В^nstackel{H} B^{n-k}$ является отображением на все пространство $B^{n-k}$ . Для систематической матрицы H это практически очевидно. Действительно, для любого $yB^{n-k}$ можно найти (построить) xB^n , такой, что y=Hx .

Разбиение пространства Bn на классы равнообразности

Рис.
7.8.
Разбиение пространства Bn на классы равнообразности

Произведение Hx, x in B^n называется синдромом [29], [33]. Фактически, синдромом вектора xin B^n является образ этого вектора при отображении — $В^n stackrel{H} B^{n-k}$ . Все векторы , имеющие один синдром, образуют класс. Так как синдром $s = Hx in B^{n-k}$ имеет размерность n-k , всего существует $2^{n-k}$ классов (если проверочная матрица имеет ранг n-k , в частности, если матрица имеет систематический вид). Из определения линейного кода следует, что класс, которому соответствует нулевой синдром, является кодом . Каждый класс C_i , отличный от кода, порождается «сдвигом» C_i =C+a_i кода на один из векторов 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 , можно представить в виде суммы кодового вектора и вектора, имеющего синдром . Представление такого вида не является единственным. Некодовый вектор a_i в этой сумме можно рассматривать как вектор ошибок, произошедших в тех разрядах кодового слова , в которых соответствующие компоненты вектора a_i равны 1. Из всех векторов ошибок, имеющих один синдром, наиболее вероятным является вектор l_s (векторы) с минимальным весом (числом единичных компонент). Такой вектор (векторы) называется лидером класса.

Алгоритм декодирования заключается в следующем. Если получен вектор и Ну = s ne 0 , считаем, что ошибкам соответствует наиболее вероятный вектор из класса C_s , то есть лидер l_s класса C_s . Тогда декодирование осуществляется в вектор z=у-l_s=У+l_s , получающийся из принятого вектора удалением лидера.

Рассмотрим пример построения кода по заданной проверочной матрице и декодирования полученного сообщения по синдрому. Пусть дана проверочная матрица $H=begin{pmatrix}1&1&1&0\ 1&0&0&1end{pmatrix}$ . Запишем уравнение для определения кодовых векторов (слов) для данной матрицы:

$begin{cases}x_1+x_2+x_3=0\x_1+x_4=0end{cases}Rightarrow begin{matrix}x_3=x_1+x_2\x_4=x_1end{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_4end{pmatrix}=begin{pmatrix}1&0\0&1\1&1\1&0end{pmatrix}*{x_1 choose x_2},$

где x_1 и х_2 — информационные разряды, а $begin{pmatrix}1&0\0&1\1&1\1&0end{pmatrix}$ — порождающая матрица, столбцами которой являются кодовые векторы.

Кодовые слова, рассматриваемые как векторы-столбцы, образуют матрицу кода

$C=begin{pmatrix}0&0&1&1\ 0&1&0&1\ 0&1&1&0\ 0&0&1&1end{pmatrix}$

Расстояние кода rho_C равно минимальному весу ненулевого слова rho_C =2 .

Найдем смежные классы, которые состоят из векторов пространства В^4 , имеющих одинаковый синдром, и выберем в каждом классе лидера (вектор из класса с минимальным весом).

Синдромом является любое возможное значение произведения Н*х .

В данном случае имеется 4 синдрома: {0 choose 0}, {0 choose 1}, {1 choose 0}, {1 choose 1} .Каждому синдрому соответствует смежный класс, синдром соответствует коду. Смежные классы (столбцы матриц) для каждого синдрома и выбранные лидеры приведены в таблице.

В третьем смежном классе — два потенциальных лидера с весом (нормой), равным 1. Один из них выбирается в качестве лидера произвольно.

Рассмотрим на этом примере процесс декодирования полученного вектора (слова) с использованием синдромов. Пусть передавался кодовый вектор $begin{pmatrix}0\1\1\0end{pmatrix}$ и в процессе переачи произошла ошибка в первом разряде. Это означает, что на приемном конце был получен вектор $у=begin{pmatrix}1\1\1\0end{pmatrix}=begin{pmatrix}0\1\1\0end{pmatrix}+begin{pmatrix}1\0\0\1end{pmatrix}$ , полученный из переданного вектора $begin{pmatrix}0\1\1\0end{pmatrix}$ в результате добавления вектора ошибки $begin{pmatrix}1\0\0\0end{pmatrix}$ (ошибка в первом разряде). Определим синдром, вычислив произведение Н*y . В данном случае получим H*y={1 choose 1} . Это означает, что полученный вектор водит в четвертый смежный класс (см. таблицу). Лидером этого смежного класса является вектор $l=begin{pmatrix}1\0\0\0end{pmatrix}$ , соответствующий данному синдрому. Вычитая (добавляя) лидер к принятому вектору, производим декодирование $y-l=y+l=begin{pmatrix}0\1\1\0end{pmatrix}$ В данном случае декодирование выполнено правильно.

Источник

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:59, 14 мая 2016.

Определение

Определение «Определение — Cиндром вектора»
Пусть — проверочная матрица: для Пусть — произвольный вектор. — синдром (не зависит от исходного кодового слова).

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

, где:
— ошибка,
— кодовое слово с ошибкой.

Смежные классы, синдром смежного класса. Лидеры смежного класса

абелева группа, где — подгруппа.

Введем смежный класс по аддитивной подгруппе .

Заметим:

— синдромы совпадают для всех векторов из одного и того же класса смежности.

Теорема Теорема о синдроме смежного класса
Два вектора и принадлежат одному и тому же смежному классу тогда и только тогда, когда их синдромы равны.
Доказательство
Два элемента группы и принадлежат одному и тому же смежному классу тогда и только тогда, когда есть элемент подгруппы, которой в данном случае является кодовое векторное пространство. Если кодовое пространство — это нулевое пространство матрицы , то вектор принадлежит кодовому пространству тогда и только тогда, когда: Поскольку для умножения матриц справедлив дистрибутивный закон, то Т.о. вектор является кодовым вектором тогда и только тогда, когда синдромы векторов и равны. ч.т.д.

Синдромов столько же, сколько существует смежных классов:

Декодирование по синдрому. Стандартное расположение линейного кода

Пусть — линейный -код, — нулевой вектор и — остальные кодовые векторы. Тогда таблицу декодирования можно составить следующим образом. Кодовые векторы располагаются в виде строки с нулевым вектором слева. Затем один из оставшихся наборов длины , например , помещается под нулевым вектором. (Обычно это бывает один из наборов, которые наиболее вероятно получить на выходе, если по каналу передавался нулевой вектор.) Далее строка заполняется так, чтобы под каждым кодовым вектором — помещался вектор . Аналогично в первый столбец второй строки помещается вектор и строка заполняется таким же способом. Процесс продолжается до тех пор, пока каждый возможный набор длины не появится где-нибудь в таблице. Это стандартное расположение, конечно, в точности совпадает с таблицей смежных классов. Строки являются смежными классами, а векторы в первом столбце — образующими смежных классов.

Пусть передавался вектор , а получен вектор .
Если , где — — образующий -го смежного класса, то вектор должен находиться в стандартном расположении в -м смежном классе под кодовым словом и и поэтому будет правильно декодирован. Если же вектор не является образующим смежного класса, то вектор должен находиться в некотором смежном классе, например -м, с образующим . Тогда вектор расположен в -й строке, но не под вектором , потому что .

Процесс декодирования может быть значительно упрощен за счет использования таблицы декодирования:

Таблица строится так, что в ней приводятся образующие смежных классов и синдромы для каждого из смежных классов. После того как получен вектор, вычисляется его синдром. Затем по таблице отыскивается образующий смежного класса, являющийся предполагаемым набором ошибок; вычитание его из полученного вектора дает предположительно посланный кодовый вектор. Хотя в большинстве случаев такая процедура во много раз уменьшает требования к объему памяти при осуществлении декодирования, этот объем все-таки может быть очень большим. Например, для двоичного (100,80)-кода требуется таблица декодирования с входами, что конечно, далеко выходит за пределы разумного. Число смежных классов равно — величине, много меньшей, но тем не менее все еще совсем нереальной.

Теорема Утверждение
Пусть — линейный двоичный -код (т. е. групповой код), используемый для передачи по двоичному симметричному каналу. Предположим, что все кодовые векторы имеют одну и ту же вероятность быть переданными. Тогда средняя вероятность правильного декодирования совпадает с наибольшей возможной для этого кода, если в качестве таблицы декодирования используется стандартное расположение, в котором каждый образующий смежного класса имеет минимальный вес в своем классе.
Доказательство
Обозначим через вектор, стоящий в -й строке и -м столбце таблицы декодирования. Кодовое слово в верхней строке столбца обозначим через ,-. Обозначим через расстояние Хэмминга между полученным вектором и кодовым словом , в которое он преобразуется при декодировании. Тогда вероятность правильного декодирования, если было передано слово , равна где — вероятность ошибки в канале, a . Поскольку имеется кодовых слов, которые предполагаются равновероятными, то при осреднении вероятности правильного декодирования используется весовой множитель : Каждому возможному двоичному вектору на выходе в этой сумме соответствует одно слагаемое, и каждое из этих слагаемых принимает максимальное значение, если соответствующий вектор декодируется в ближайший кодовый вектор в смысле Хэмминга, так как есть монотонно убывающая функция от . Поэтому вероятность правильного декодирования будет максимальной, если каждый полученный вектор будет преобразовываться в ближайший кодовый вектор. Предположим теперь, что некоторый вектор расположен в таблице декодирования под кодовым вектором , так что расстояние Хэмминга между ними равно . Допустим, что ближайший кодовый вектор находится на расстоянии . Пусть — образующий смежного класса, содержащего вектор . Тогда вес вектора равен . Элемент имеет вес и лежит в том же самом смежном классе. Поскольку предполагалось, что имеет минимальный вес в своем смежном классе, то , и поэтому лежит по крайней мере так же близко к , как и к . Число образующих смежных классов веса обозначим через . Вероятность правильного декодирования может быть записана тогда следующим образом:

Литература

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.

Источник

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

Отображение является отображением на все пространство . Для систематической матрицы H это практически очевидно. Действительно, для любого можно найти (построить) , такой, что .

Рис. 7.8.Разбиение пространства Bn на классы равнообразности

Произведение называется синдромом [29], [33]. Фактически, синдромом вектора является образ этого вектора при отображении -. Все векторы , имеющие один синдром, образуют класс. Так как синдром имеет размерность , всего существует классов (если проверочная матрица имеет ранг , в частности, если матрица имеет систематический вид). Из определения линейного кода следует, что класс, которому соответствует нулевой синдром, является кодом . Каждый класс , отличный от кода, порождается «сдвигом» кода на один из векторов класса . Действительно, если ., то есть , тогда и, следовательно, и , где — кодовое слово. Таким образом, любой некодовый вектор, имеющий синдром , можно представить в виде суммы кодового вектора и вектора, имеющего синдром . Представление такого вида не является единственным. Некодовый вектор в этой сумме можно рассматривать как вектор ошибок, произошедших в тех разрядах кодового слова , в которых соответствующие компоненты вектора равны 1. Из всех векторов ошибок, имеющих один синдром, наиболее вероятным является вектор (векторы) с минимальным весом (числом единичных компонент). Такой вектор (векторы) называется лидером класса.

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

Рассмотрим пример построения кода по заданной проверочной матрице и декодирования полученного сообщения по синдрому. Пусть дана проверочная матрица . Запишем уравнение для определения кодовых векторов (слов) для данной матрицы:

и которые можно рассматривать как информационные разряды, задаются произвольно (всего 4 варианта 00, 01, 10, 11), а проверочные разряды и определяются через и . В итоге все кодовые слова определяются из выражения

где и — информационные разряды, а — порождающая матрица, столбцами которой являются кодовые векторы.

Кодовые слова, рассматриваемые как векторы-столбцы, образуют матрицу кода

Расстояние кода равно минимальному весу ненулевого слова .

Найдем смежные классы, которые состоят из векторов пространства , имеющих одинаковый синдром, и выберем в каждом классе лидера (вектор из класса с минимальным весом).

Синдромом является любое возможное значение произведения .

В данном случае имеется 4 синдрома: .Каждому синдрому соответствует смежный класс, синдром соответствует коду. Смежные классы (столбцы матриц) для каждого синдрома и выбранные лидеры приведены в таблице.

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

Лекция 8

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

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

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

Источник

Декодирование линейного кода по синдрому

Разбиение пространства Bn на классы равнообразности

Рис.
7.8.
Разбиение пространства Bn на классы равнообразности

$begin{cases}x_1+x_2+x_3=0\x_1+x_4=0end{cases}Rightarrow begin{matrix}x_3=x_1+x_2\x_4=x_1end{matrix}$

$begin{pmatrix}x_1\x_2\x_3\x_4end{pmatrix}=begin{pmatrix}1&0\0&1\1&1\1&0end{pmatrix}*{x_1 choose x_2},$

Кодовые слова, рассматриваемые как векторы-столбцы, образуют матрицу кода

$C=begin{pmatrix}0&0&1&1\ 0&1&0&1\ 0&1&1&0\ 0&0&1&1end{pmatrix}$

Расстояние кода rho_C равно минимальному весу ненулевого слова rho_C =2 .

Синдромом является любое возможное значение произведения Н*х .

Источник