смежные классы линейных кодов

Декодирование линейных кодов

Вектор е из соотношения (2.13) называется вектором ошибок.

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

Далее для определения одного из алгоритмов декодирования нам понадобятся дополнительные сведения из алгебры.

2. Непустое подмножество Н группы (G, *) называется подгруппой группы (G, *), если Н является группой относительно той же групповой операции *.

В качестве примера подгруппы можно привести множество всех четных чисел в группе % всех целых чисел относительно операции арифметического сложения.

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

Пример 2.1.5. Пусть G = <0,1,2,3>— аддитивная абелева группа с групповой операцией, задаваемой следующей таблицей:

Легко проверить, что элементы 0 и 2 образуют множество, замкнутое относительно групповой операции группы G:

Остальные аксиомы групп также имеют место для указанных элементов. Таким образом, элементы 0 и 2 группы 6 образуют подгруппу Н = <0, 2 > относительно групповой операции исходной группы G.

Таким образом, необходимым и достаточным условием того, что непустое подмножество Н элементов группы G образует подгруппу, является выполнение для любых двух элементов а и Ь из Н следующих условий:

Кроме того, следует отметить, что единичный элемент подгруппы всегда совпадает с единичным элементом исходной группы [8].

Очевидно, что подмножество <е>любой группы G, состоящее только из единичного элемента, а также сама группа G удовлетворяют условиям образования подгруппы. Такие подгруппы называются тривиальными подгруппами.

называется правым смежным классом группы G по подгруппе Н, порождаемым элементом g. Аналогично множество

называется левым смежным классом группы G по подгруппе Н, порождаемым элементом g.

Предположим, что два элемента одного и того же смежного класса группы G

по подгруппе Н равны: gi*hj = gi*hk. Тогда умножение слева на g;

1 дает равенство hj = hk. Но это противоречит определению подгруппы.

Предположим теперь, что два элемента двух смежных классов g;*H и gk*H

равны: gi*hj = gk*h_s. Умножение справа на hj— 1 дает равенство g; = gk*h_s*hj

Рассмотрим теперь смежный класс:

В силу замкнутости Н относительно операции *, элемент h_s*hj-‘ l *h также принадлежит Н. Обозначив h_s*hj-‘*h = h‘, получим:

Итак, рассматриваемые элементы g/ и g* порождают один и тот же смежный класс группы G по подгруппе Н.

Таким образом, смежные классы группы G по подгруппе Н, содержащие хотя бы один общий элемент, совпадают.

Из двух последних соотношений также следует, что число повторяющихся смежных классов группы G по подгруппе Н для каждого элемента g группы G соответствует порядку подгруппы Н.

Для получения смежного класса, совпадающего с некоторым исходным смежным классом g/c* Н и порождаемого отличным от gk элементом G, в качестве порождающего элемента можно взять любой элемент gj-g к* hj данного смежного класса g/c* Н, где е.

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

Таким образом, векторное подпространство GF k (q) кода С разбивает исходное векторное пространство GF n (q) на непересекающиеся смежные классы, определяемые следующим образом:

Как было показано в предыдущем пункте этого подпараграфа, число элементов каждого смежного класса совпадает с числом кодовых слов кода С. Иными словами, каждый смежный класс а + С содержит q k элементов. Число всех непересекающихся смежных классов определяется соотношением (2.15) и имеет значение q n

Таким образом, векторное пространство GF n (q) можно представить как объединение множеств:

где a s ), s = 0,1. q n

(не пересекающиеся) смежные классы.

Будем считать, что в соотношении (2.16) а(°) = 0. Тогда смежный класс а(°) + + С совпадает с кодом С.

Как было показано в предыдущем пункте этого подпараграфа, каждый смежный класс вида (2.16) может быть порожден q k различными элементами (векторами) векторного пространства GF n (q).

Пример 2.1.7. Рассмотрим построение отличных от исходного кода смежных классов двоичного линейного (6, 3)-кода С из примера 2.1.4.

Множество всех кодовых слов в данном случае содержит восемь элементов (векторов) векторного пространства GF 6 (2), которые можно представить в виде двоичных последовательностей длиной не более шести двоичных символов:

Число элементов (векторов) каждого смежного класса соответствует числу q k = 8 кодовых слов кода С.

Пусть, например, а = 000001. Тогда смежный класс а + С будет состоять из следующих элементов (векторов):

Нетрудно проверить, что то же множество векторов может быть получено при а = 001100, 010010, 011111, 100111,101010,110100,111001. То есть при любом другом отличном от исходного порождающего элемента а значении, принадлежащем указанному смежному классу.

Согласно соотношению (2.16), число не пересекающихся смежных классов в этом случае: q n

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

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

Любой элемент (вектор) каждого смежного класса, как и сам смежный класс, может быть получен восемью различными способами как а + с для восьми различных значений порождающего элемента а и всех восьми кодовых слов с кода С. Например, элемент 111001 рассмотренного выше в этом примере смежного класса, порожденного элементом а = 000001, может быть получен как а + с для значений а = 000001, 001100, 010010, 011111, 100111, 101010, 110100, 111001 и с = 111000, 110101, 101011, 100110, 011110, 010011, 001101, 000000 соответственно.

Как было показано выше в этом подпараграфе, вектор v всегда принадлежит одному из q n

k не пересекающихся смежных классов вида (2.16). При отсутствии ошибок вектор v принадлежит смежному классу, совпадающему с кодом С. При ненулевом векторе ошибок вектор i/оказывается в другом смежном классе а + С (пока будем считать, что вес вектора ошибок не превосходит максимального числа t исправляемых кодом ошибок).

Принимая вектор е за порождающий элемент смежного класса е + С, по известному вектору v мы можем определить q k возможных значений вектора е. Очевидно, наиболее вероятным является значение е наименьшего веса.

Элемент (вектор) минимального веса в смежном классе а + С называется лидером смежного класса а + С.

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

В этом случае аппаратная реализация декодера основана на так называемом табличном методе и требует хранения в памяти устройства всех смежных классов и их лидеров. Подобного рода декодер даже при небольшой длине кода требует значительных аппаратных затрат. Например, для рассмотренного в примерах 2.1.4 и 2.1.7 двоичного линейного (6, 3)-кода требуется хранить в памяти декодера q n

k = 8 смежных классов по q k = 8 двоичных векторов длины п = 6 символов.

Однако табличный декодер может быть несколько упрощен.

Таким образом, в силу равенства синдромов s(v) и s(e), вектор v принятого сообщения и вектор ошибок е всегда принадлежат одному смежному классу и по известному синдрому s(v) можно однозначно определить лидер соответствующего смежного класса.

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

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

Пример 2.1.8. Рассмотрим снова двоичный линейный (6, 3)-код из примеров 2.1.4 и 2.1.7.

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

Лидер смежного класса

< 1, 12, 18,31,39, 42, 52, 57 >

< 2, 15, 17, 28, 36,41,55, 58 >

< 4, 9, 23, 26, 34,47, 49, 60 >

Нетрудно убедиться в том, что синдром любого элемента каждого смежного класса совпадает с синдромом лидера этого смежного класса.

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

Кроме того, в одном (последнем) смежном классе три лидера веса 2. Это позволяет с небольшой (1/3) вероятностью декодировать двойную ошибку (при условии, что вероятности всех векторов принимаемых сообщений с двойной ошибкой равны).

Очевидно, избыточность рассмотренного в примерах 2.1.4, 2.1.7 и 2.1.8 двоичного линейного (6, 3)-кода немного превышает накладываемые на него корректирующие свойства, так как помимо достаточных для декодирования лидеров смежных классов веса 1 в одном из смежных классов имеют место лидеры веса 2.

Если в качестве лидеров q n

k смежных классов кода удается взять векторы веса t и менее и только их, то код называется совершенным кодом. Если же в качестве лидеров q n

k смежных классов кода удается взять все необходимые для исправления не менее t ошибок векторы веса t и менее, а также несколько векторов веса t + 1, то код называется квазисовершенным кодом.

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

Возвращаясь к примеру 2.1.4, отметим, что в случае двоичного линейного

Тогда порождающая матрица:

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

Этот вывод подтверждается неравенством (2.5), так как минимальное расстояние (5, 3)-кода равно двум и, следовательно, ни одно целое положительное значение t исправляемых кодом ошибок данному неравенству не удовлетворяет.

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

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

Если же число ошибок превосходит t и принятый вектор попадает в смежный класс, отличный от смежного класса кода, то декодирование возможно лишь с некоторой (обычно небольшой) вероятностью. При этом возможны два способа декодирования:

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

В силу указанных особенностей мы будем рассматривать только неполные декодеры.

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

Например, для линейного (31, 26)-кода над GF(2) требуется определить 32 смежных класса по 67108864 вектора длины 31 в каждом и найти лидеры каждого смежного класса.

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

Однако мы можем заранее определить некоторый удобный метод декодирования и на его основе построить линейный код специального вида.

Источник

12. Декодирование по синдрому и еще раз о коде Хемминга

Слово «синдром» означает обычно совокупность признаков, характерных для того или иного явления. Такой же примерно смысл имеет понятие «синдром» и в теории кодирования. Синдром вектора, содержащего, быть может, ошибки, дает возможность распознать наиболее вероятный характер этих ошибок. Правда, определение, которое мы приводим ниже, не сразу позволяет это увидеть. Синдромом вектора и называется вектор s(u), определяемый равенством:

Пусть теперь вектор u не является кодовым, тогда этот вектор обязательно содержит ошибочные символы. Вектор и можно представить тогда в виде суммы посланного кодового вектора υ (который пока не известен) и вектора ошибки е:

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

На языке теории групп это означает, что U есть смежный класс по подгруппе V (пространство L_n и его кодовое подпространство V можно рассматривать соответственно как группу и ее подгруппу относительно операции сложения векторов).

Сказанное позволяет сделать следующие выводы:

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

2. Вектор ошибки e для вектора u нужно искать в силу равенства (2) в том же смежном классе, которому принадлежит и сам вектор u.

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

При реализации алгоритма декодирования по синдрому составляют таблицу, в которой указываются синдромы s_i и лидеры e_i соответствующих им смежных классов. Алгоритм декодирования заключается тогда в следующем:

1. Вычисляем синдром s(u) принятого вектора u.

2. По синдрому s(u) = s_i определяем из таблицы лидер e_i соответствующего смежного класса.

3. Определяем посланный кодовый вектор υ как разность

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

Алгоритм исправления одиночных ошибок в этом случае удивительно прост. Если вектор и содержит ошибочный символ в i-й позиции, то синдром s(u) этого вектора совпадает с i-м столбцом проверочной матрицы. Таким образом, этот синдром, читаемый как двоичное число, и есть номер ошибочного символа.

Например, из приведенной выше проверочной матрицы для (15,11)-кода Хемминга получается следующая проверочная матрица для расширенного (16,11)-кода:

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

Во втором случае считаем, что допущены две или любое большее четное число ошибок, если s(u) ≠ 0. Если же s(u) = 0, то, как обычно, полагаем, что ошибок при передаче не было.

Источник

Простейший алгоритм декодирования линейных кодов

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

Пусть сообщение й = <щи₂. и_к> закодировано в кодовое слово х = = <х₁х₂. х„>, которое передается по каналу связи. Так как в канале действуют помехи, то принятый вектор У = <уУ2—Уп) может отличаться от переданного х. Разность между векторами е =у — х = <е₁е₂. е„> называется вектором ошибок. Если е, = 0, то i-Й символ правильный.

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

Для построения алгоритма работы декодера вводят три важных определения:

Например, р(х,у) = р( 10111,00101) = w/(10111-00101) = м(ЮОЮ) = 2. (Напомним, что все операции над векторами выполняются в двоичной системе счисления).

3. Кодовое расстояние d в подпространстве определяется, как минимальное расстояние между кодовыми словами: d < V]= min р<х, у).

Расстояние с1<У) можно определить, зная минимальный вес ненулевого вектора кодового подпространства . Действительно, если хе <Г>и уе<У>, то и их разность 2 = (х-у) также принадлежат подпространству <У>, поскольку код линеен. Значит, для нахождения минимального расстояния между кодовыми словами нет необходимости перебирать все значения г. Следует найти минимальный вес вектора в подпространстве <У>. Эта величина и будет являться кодовым расстоянием подпространства <У>.

Введенные понятия расстояния между векторами и веса вектора называются расстоянием и весом Хэмминга. Расстояние р(х,у) обладает следующими свойствами:

На рис.2.2, изображенном ниже, приведена геометрическая интерпретация четвертого свойства расстояний по Хеммингу.

На понятии кодового расстояния по Хеммингу основывается оценка возможностей кода по исправлению ошибок. Пусть передан вектор сообщения х, принадлежащий подпространству кодовых слов <У>. При передаче этого вектора он был искажен помехами, и был принят вектор у е < Ь_п>. Алгоритм исправления ошибок основывается на том, чтобы из всех векторов подпространства был выбран такой вектор х, чтобы расстояние р<х, у) было минимально возможным.

Основываясь на четвертом свойстве можно утверждать, что если расстояние р <х, у)окажется меньше (2/2, то расстояние р(у 2) между другими векторами 2 е <У> и принятым вектором у, заведомо окажутся больше чем (1/2. Иными словами, принятый вектор у можно полагать вектором х, который при передаче был искажен помехой. Сказанное можно сформулировать следующим образом: если кодовое расстояние обозначить как с1 = 2/,

где знак [•] означает целую часть числа, записанного в скобках.

Два кода <У_у> и <У₂> называются эквивалентными, если их кодовые слова одинакового веса. Имея код < У_х>, можно получить эквивалентный ему код <У₂> простой перестановкой столбцов матрицы ((71), порождающей код <У1>. В самом деле, при перестановке столбцов порождающей матрицы (СО поменяется положение элементов в кодовых словах соответствующих этим столбцам. Вес кодовых слов при этом остается неизменным.

Пример эквивалентных кодов ((71) и (62):

Преобразованием порождающей матрицы для всякого кода <У_х> можно отыскать эквивалентный ему систематический код <У₂>.

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

Пример. Пусть дана порождающая матрица кода (8,4):

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

Далее, складываем первую и вторую строки, и заменив их суммой первую строку, приходим к матрице:

Простейший алгоритм декодирования. При описании работы декодера удобно пользоваться так называемым стандартным расположением кода. Пусть дано множество <V> из 2 к кодовых векторов (п,к) в пространстве векторов <Ь_п>. Для любого вектора А е <Ь_п> множество А + х (где х е <V>) называется смежным классом кода . Каждый смежный класс содержит 2 к векторов (по числу векторов пространства ).

Можно доказать [4], что два смежных класса, образованных векторами Л е и В е<Ь_п> либо не пересекаются (т.е. не имеют общих элементов),

либо совпадают. Число различных смежных классов равно 2 п

Теперь предположим, что декодер принимает вектор у, состоящий из переданного слова х и ошибки е. Этот вектор у принадлежит одному из смежных классов, у = х + е, где х, е <V>, а е является образующим одного из смежных классов.

Определение. Ошибка с минимальным весом, образующая тот или иной смежный класс, называется лидером этого смежного класса. В найденном смежном классе декодирование принятого вектора у производится по алгоритму: х = у + е₍, где ? _<— лидер смежных классов.

Пример. Пусть дан код (4,2) с порождающей матрицей (С); поверочной матрицей кода (Я):

Этот код имеет смежные классы, изображенные в таблице 2.1.

-1. Общее же число возможных помех составляет 2″.

Заметим, что все векторы пространства <Ь_п> разбиты на четыре смежных класса, образующих строки таблицы. Лидеры смежных классов расположены в первом столбце таблицы. В третьем смежном классе имеются два лидера 0100 и 0001. В такой ситуации можно выбирать любой из них (в примере выбран первый лидер).

Таблица 2.1. смежные классы кода (4,2)

Сообщение Лидер х смежных классой^

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

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

матрица; — транспонированный принятый век

тор. По найденному синдрому 5 определяют, какому смежному классу принадлежит принятый вектор у.

(по определению проверочной матрицы).

3. Синдром принятого вектора у равен синдрому вектора ошибки:

имеют один и тот же синдром. Действительно, если Уі иу і располагаются в одном смежном классе, то их разность и

поэтому,

Пример декодирования кода(4,2). Возможные помехи и вычисленные для них синдромы приведены в табл.2.2.

Таблица 2.2. Возможные помехи для кода (4,2) и их синдромы

Теперь распределим помехи по смежным классам. Количество смежных классов для рассматриваемого примера составит 2 п

Таблица 2.3. Распределение помех кода (4,2) по смежным классам

Достоверность декодирования. Вероятность появления неправильного кодового слова на выходе декодера называется вероятностью ошибки в приеме кодового слова. Будем считать, что алгоритм работы декодера таков, что те ошибки, которые являются лидерами смежных классов исправляются при декодировании, а остальные нет. Следует помнить, что количество исправляемых ошибок (а значит и лидеров смежных классов) должно удовлетворять неравенству . Тогда вероятность ошибки в принятом слове

равна:

классов, лидер которых имеет вес г).

Как и в предыдущем примере, положим, что в основе алгоритма работы декодера положена табл.2.1. Тогда, используя таблицу смежных классов (2.1), на примере кода (4,2) определим вероятность ошибки на информационный бит. Предположим, что по каналу не передается никакого сообщения, однако на выходе декодера появились информационные биты 11. Эти символы обусловлены воздействием на декодер помех, действующих в канале. Напомним, что на четвертом этапе работы декодера из четырехбитового вектора х, который считается восстановленным канальным словом, отделяют первые два бита. Эти биты полагаются информационными.

Итак, обратимся к табл.2.1. Используя эту таблицу, можно видеть, что символы 11 на выходе декодера появляются тогда, когда на вход декодера поступает либо вектор 1110, либо ОНО, либо 1010, либо 1100. Действии- тельно, пусть на вход декодера поступает вектор у = 0110. По этому вектору

Полная вероятность (Р₀ш)и появления выходных символов 11 составляет:

Таблица 2.4. Возможные помехи и решения декодера

Источник