Учебно-методический центр языковой подготовки автф кц. Линейные блоковые коды

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

,

а выходом кодера является вектор из символов

.

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

(8.1.2)

где или , а представляют произведение и . Линейные уравнения (8.1.2)

можно также представить в матричной форме

где - порождающая матрица кода, равная

(8.1.4)

Заметим, что произвольное кодовое слово – это просто линейная комбинация векторов из ,

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

Любую порождающую матрицу кода путём проведения операций над строками (и перестановкой столбцов) можно свести к «систематической форме»:

, (8.1.6)

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

Если код порождён матрицей, не имеющей систематической формы (8.1.6), он называется несистематическим. Однако такая матрица эквивалентна матрице в систематической форме в том смысле, что одна может быть получена из другой элементарными операциями над строками и перемещением столбцов. Два линейных кода, порожденных двумя эквивалентными порождающими матрицами, называют эквивалентными и один может быть получен из другого перестановкой элементов. Таким образом, каждый линейный код эквивалентен линейному систематическому коду.

Пример 8.1.1. Рассмотрим код (7, 4) с порождающей матрицей

. (8.1.7)

Типичное кодовое слово можно выразить так:

где представляют четыре информационных бита, a представляют три паритетных бита, определённых так:

Линейный систематический двоичный блоковый кодер можно реализовать, используя -битовый регистр сдвига, сумматоров , связанных с соответствующими ячейками регистра сдвига и генерирующих проверочные символы, которые потом временно располагаются во втором регистре сдвига длины . Затем информационных бита, а за ними проверочных бита последовательно покидают два регистра и подаются на модулятор. Это кодирование иллюстрируется рис. 8.1.1 для кода (7, 4) из примера (8.1.1).

Рис. 8.1.1. Линейный регистр сдвига для получения двоичного кода (7,4)

С любым линейным кодом кодом связан дуальный код размерностью .

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

где означает вектор-столбец, состоящий из нулей, а - кодовое слово кода. Поскольку (8.1.9) справедливо для любого кодового слова кода, то следует

где - теперь матрица со всеми нулевыми элементами.

Теперь предположим, что линейный код является систематическим, и его порождающая матрица дана в систематической форме (8.1.6). Тогда, поскольку , следует, что

(8.1.11)

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

Пример (8.1.2). Для систематического кода (7, 4), генерируемого матрицей , определяемой (8.1.7), имеем согласно (8.1.11) матрицу в виде

(8.1.12)

Теперь уравнение распадается на три уравнения

(8.1.13)

Таким образом, видим, что произведение эквивалентно суммированию проверочных символов с соответствующими линейными комбинациями информационных символов, используемых для вычисления Это значит, что (8.1.13) эквивалентно (8.1.8).

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

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

1.2.2. Проверочная матрица линейного кода

Поскольку линейный код V является подпространством, то для него существует ортогональное дополнение (или нулевое подпространство ). Ортогональное дополнение V " (n , k ) - кода V состоит из всех векторов длины n , ортогональных к каждому вектору v Î V . Векторы и называются ортогональными , если их скалярное произведение равно 0. Для двоичных векторов скалярное произведение равно сумме произведений соответствующих компонент. Например, скалярное произведение (00101, 10110) векторов 00101 и 10110 есть вектор 00100 = 0×1 + + 0×0 + 1×1 + 0×1 + 1×0. Ортогональное дополнение также является подпространством и, таким образом, может рассматриваться как линейный код. Множество V " - называется кодом, дуальным или двойственным к V.

Ортогональное дополнение V " (n , k ) - кода V имеет размерность (n - k) ; соответственно любой его базис состоит из (n -k) векторов. Порождающая матрица Н ортогонального дополнения называется проверочной матрицей кода V .

Т. к проверочная матрица состоит из базисных векторов ортогонального дополнения, то двоичный вектор с является кодовым словом, если и только если сН T = 0. Таким образом, проверка на наличие ошибок при передаче кодового слова сводится к умножению двух матриц вместо перебора всех кодовых слов. Умножение матриц, размерность которых составляет несколько тысяч, при современной вычислительной технике выполняется очень быстро.

Проверочную матрицу можно построить путем нахождения фундаментальной системы решений для соответствующей системы уравнений. Матрица

из предыдущего раздела порождает следующую систему уравнений:

Основная матрица системы совпадает с матрицей G . Неизвестные x 1 , x 2 и x 3 , для которых существует минор, не равный 0, можно объявить главными неизвестными. Тогда неизвестные x 4 и x 5 являются свободными. Мы выбираем для них линейно независимые значения 01 и 10 и получаем системы уравнений:

и

Из первой системы получаем x 1 = 1, x 2 = 0, x 3 = 1, т. е. решением исходной системы является вектор 10101. Из второй системы получаем x 1 = 1, x 2 = 1, x 3 = 0, т. е. вторым решением в фундаментальной системе решений является вектор 11010. Таким образом, получаем проверочную матрицу:

.

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

Связь кодового расстояния линейного кода и проверочной матрицы устанавливается следующей теоремой:

Теорема 1.3. Каждое не нулевое кодовое слово имеет вес не менее w , тогда и только тогда, когда любая совокупность из w столбцов матрицы Н

Доказательство. Для любого кодового слова с выполняется равенство сН T = 0. Пусть кодовое слово с имеет вес u . Исключим из рассмотрения нулевые компоненты вектора. Полученное равенство будет соотношением линейной зависимости u столбцов из Н . Следовательно, Н содержит множество из u линейно зависимых столбцов. Таким образом, в коде существует слово веса u , если и только если в матрице Н существует совокупность из u линейно зависимых столбцов. Таким образом, все не нулевые слова кода имеют вес не меньше w w -1 столбцов матрицы Н является линейно независимой.

Как следствие теорем 1.1 и 1.3 имеет место следующее утверждение:

Следствие. Расстояние линейного кода не менее w , если и только если любая совокупность из w -1 столбцов матрицы Н является линейно независимой.

Согласно сформулированным выше утверждениями, для того чтобы найти (п ,k )-код, исправляющий t ошибок, достаточно построить матрицу Н размерности (п - k ) × n , в которой любые 2 t столбцов линейно независимы.

Линейный систематический блочный код может быть также определён проверочной матрицей H , обладающей следующими свойствами. Если некоторая последовательность u является кодовым словом , то , т.е. проверочная матрица H ортогональна любой кодовой последовательности данного кода .

Проверочная матрица имеет размерность (n -k )×n и следующую структуру:

, (3.4)

проверочная часть единичная

матрицы подматрица

где
– транспонированная проверочная подматрица порождающей матрицы G ( k x n ) ;
- единичная подматрица.

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

Пример. Для рассмотренного примера линейного блочного (4, 7)-кода проверочная матрица имеет вид

.

Пусть принята последовательность с =(1011001). Проверим, является ли она кодовым словом:

=(1011001)
=(1 0 1 ) ≠ 0 .

Следовательно, последовательность (1011001) не является кодовым словом данного кода.

^

3.7 Синдром и обнаружение ошибки линейным блочным кодом

Пусть x =(х 1 , х 2 , …, х n ) – кодовое слово , переданное по каналу с помехами;

y =(y 1 , y 2 , …, y n ) – принятая последовательность, которая в силу влияния помех может отличаться от переданной.

Для описания возникающих в канале ошибок используется вектор ошибок е= (e 1 , e 2 , …, e n ) , который представляет собой двоичную последовательность длиной n с единицами в тех позициях, в которых произошла ошибка.

Например, вектор ошибок е =(0 0 0 1 0 0 0 ) означает однократную ошибку в четвертом бите, е =(1 1 0 0 0 0 0 ) – двукратную ошибку в первом и втором битах.

При передаче кодового слова x по каналу с шумом принятая последовательность будет иметь вид

y = x +е , (3.5)

где x - переданное кодовое слово; e – вектор, описывающий ошибки в канале.

Например, x =(0 0 0 1 0 0 0 ), e =(0 0 0 1 0 0 0 ). Тогда y =(0 0 0 0 0 0 0 ).

Чтобы проверить наличие ошибок в принятом векторе y , декодер вычисляет следующую (n -k ) - последовательность

S =(S 1 , S 2 , … S n - k )=y 
, (3.6)

где y – принятая кодированная последовательность; – проверочная матрица данного кода.

При этом вектор y является кодовым словом тогда, когда S =(0 0 … 0 ), и не является кодовым словом данного кода , если S ≠0.

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

Некоторые сочетания ошибок, используя синдром, обнаружить невозможно. Например, если переданное кодовое слово x под влиянием помех превратилось в другое кодовое слово этого же кода, тогда синдром S =y ×
=0 , и декодер ошибки не обнаружит .

Пример. Для рассматриваемого примера линейного блочного (4, 7)-кода синдром определяют следующим образом.

Пусть x =(х 1 , х 2 , …, х 7 ) – принятая кодированная последовательность. Тогда

S =x 
=(х 1 ,х 2 ,… , х 7 )×
=((x 1 +x 3 +x 4 +x 5 ) , (x 1 +x 2 +x 3 +x 6 ) , (x 2 +x 3 +x 4 +x 7 ) ).

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

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

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

Такой способ описания кодов применим для любых, а не только линейных кодов. Однако, при больших к размер кодовой таблицы оказывается слишком большим, чтобы им пользоваться на практике.

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

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

Линейный блочный (л, /с)-код полностью определяется матрицей G размером к х п с двоичными матричными элементами. При этом каждое кодовое слово является линейной комбинацией строк матрицы G, а каждая линейная комбинация строк G - кодовым словом.

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

Например, для простейшего (4, 3)-кода с проверкой на четность порождающая матрица будет иметь вид:

Пусть т - (т 1; т 2 , ..., т к) будет тем блоком-сообщением, который необходимо закодировать с использованием данного кода.

Тогда соответствующим ему кодовым словом U будет

С учетом структуры матрицы G символы кодового слова и будут такими:

Иными словами, к крайних левых символов кодового слова совпадают с символами кодируемой информационной последовательности, а остальные (п - к) символов являются линейными комбинациями символов информационной последовательности.

Например, если входная последовательность кодера т = = (10 1), то с применением порождающей матрицы код будет построен так:

8 Командир послал трех разведчиков по первой дороге, трех - по второй, двух - по третьей, по четвертой пошел сам. Составить порождающую матрицу такого кода.

Ответ: по сюжету задачи сообщение, полученное командиром лично, не может быть искаженным. Поэтому ограничимся исследованием информации, передаваемой бойцами. В группе, отправившейся по одной из дорог, каждый боец должен доложить командиру либо об обнаружении объекта (обозначим такой доклад «1»), либо об отсутствии объекта («0»). При отсутствии искажений доклады каждого бойца из одной и той же группы должны совпадать. Следовательно:

Матрицу можно привести к каноническому виду, перенумеровав бойцов, т.е. по первой дороге послав первого, четвертого и пятого, по второй дороге - второго, шестого и седьмого, по третьей дороге-третьего и восьмого бойцов. Получим следующую порождающую матрицу:

Определенный таким образом код называется линейным блочным систематическим (п, /cj-кодом с обобщенными проверками на четность.

Так как, согласно определению, линейный (л, /с)-код длины п над GF(q) является подпространством GF k (q) векторного пространства GF n (q), то должно существовать ортогональное дополнение подпространства GF k (q) линейного кода (см. подпараграф 1.7.1).

Пусть Н - матрица, строки которой соответствуют базисным векторам ортогонального дополнения g-ичного линейного кода С длины п. Тогда для любого вектора с, принадлежащего коду, справедливо:

Условие (2.10) позволяет проверить принадлежность произвольной л-после- довательности элементов GF(q) определенному g-ичному линейному коду.

Если вектор линейного кода имеет вес Хэмминга шо, то это значит, что в кодовом слове присутствует шо ненулевых символов (согласно определению веса Хэмминга, см. подпараграф 2.1.4). Тогда, согласно правилам умножения матриц, произведение вектора с со значением шо веса Хэмминга на матрицу Н т соответствует линейной комбинации шо столбцов матрицы Н. При этом равенство (2.10), очевидно, имеет место тогда и только тогда, когда шо столбцов матрицы Н линейно зависимы.

Таким образом, условием существования во множестве кодовых слов некоторого линейного кода кодового слова с весом Хэмминга шо является наличие в матрице Н линейно зависимых столбцов в количестве шо. Из этого следует также, что линейный код имеет минимальный вес (см. подпараграф 2.1.4) не менее некоторого значения шо тогда и только тогда, когда любые шо - 1 столбцов матрицы Н линейно независимы. Следовательно, согласно неравенству (2.6), для того чтобы найти линейный код с минимальным весом шо, исправляющий t ошибок, достаточно найти матрицу Н, у которой не менее чем шо - 1 = 2-t любых столбцов были линейно независимы.

Рассмотрим подробнее матрицу Н. Как было сказано выше, строками матрицы Н являются базисные векторы ортогонального дополнения линейного кода. Если множество л-последовательностей образует подпространство размерности к, то ортогональное дополнение этого подпространства будет иметь размерность п-к (см. подпараграфы 1.7.1 и 1.7.2). Подпространство размерности п - к образуют любые п-к базисных векторов. Поэтому матрица Н должна содержать п-к линейно независимых строк.

Так как матрицы G и Н принадлежат одному пространству л-последовательностей, то число столбцов матрицы Н равно числу столбцов матрицы G. Таким образом, матрица Н имеет размер (л - к) х л. Все столбцы матрицы Н, как уже было сказано, образуют линейно независимые группы по 2t столбцов.

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

Результатом произведения матриц G размера к* ли Н т размера л х (п-к) является матрица размера к х (л - к), состоящая из нулевых элементов.

Матрица Н размера (п-к)х л, строками которой являются базисные векторы ортогонального дополнения подпространства линейного кода, называется проверочной матрицей линейного кода.

Согласно соотношению (2.4), порождающая матрица систематического линейного кода состоит из единичной матрицы порядка к и матрицы проверочных символов размера к х (л - к), которая, в свою очередь, является расширением единичной матрицы. Как показано в приложении 1, умножение двух матриц можно выполнить, разделив перемножаемые матрицы на матрицы меньшего размера (блоки) с последующим умножением отдельных блоков перемножаемых матриц. Тогда для матриц G и Н можно записать:

Число столбцов в блоках А и В матрицы Н 7 должно соответствовать числу строк в блоках Ек и Р матрицы G (по правилам умножения матриц). Результирующая матрица должна иметь размер /с * (л - к). Очевидно, что если положить А = -Р и В = Ел_/с, то матрица Н будет удовлетворять уравнению (2.11).

Таким образом, матрица Н т является расширением матрицы -Р и помимо матрицы - Р матрица Н содержит единичную матрицу порядка п - к. Матрица Н т является результатом транспонирования матрицы Н.

Результатом повторного транспонирования матрицы является исходная матрица. Поэтому матрица Н может быть получена путем транспонирования матрицы Н т. Так как для любого элемента а поля GF[ 2) справедливо а = - а, то для двоичного линейного кода справедливо Р--Р.

Матрица Н двоичного линейного кода будет иметь следующий вид:

Матрица Р, входящая в состав матрицы G и содержащая проверочные символы, может быть получена путем транспонирования матрицы Р т, входящей в состав матрицы Н.

Таким образом, построение линейного кода сводится к поиску матрицы Н. По заданной матрице Н легко найти матрицу G.

Пример 2.1.4. Рассмотрим построение двоичного линейного кода - кода над GF(2), исправляющего одну ошибку кодового слова с информационной последовательностью размера к = 3 бита.

Согласно соотношению (2.9), для кода с максимальным расстоянием r = 2-t = = 2. Тогда л = /с + г = 3 + 2 = 5. Однако, как будет показано в следующем подпараграфе, линейный двоичный (5,3)-код не способен исправлять одиночную ошибку кодового слова. При этом минимальное число избыточных символов для данного случая г = 3, а рассматриваемый код - двоичный линейный (6,3)-код.

Таким образом, в данном случае матрица Н содержит проверочную матрицу размера /сх(л-/с) = 3*3и единичную матрицу порядка п-к= 3.

Все столбцы матрицы Н должны образовывать линейно независимые группы по два столбца и линейно зависимую группу из трех столбцов. Такому условию отвечают, например, последовательности 101, 110 и 011 над GF(2). Указанные последовательности образуют столбцы матрицы Р т, входящей в состав матрицы Н. Остальные элементы матрицы Н соответствуют единичной матрице порядка 3:

Дописав к единичной матрице порядка 3 матрицу Р, полученную транспонированием матрицы Р т, получим матрицу G:

Рассмотрим теперь процесс формирования и структуру кодового слова двоичного линейного (6, 3)-кода с порождающей матрицей вида (2.12):

Три первых символа кодового слова (ci - Сз) содержат информационные символы (/ 1 - г"з), сформированные в результате умножения матрицы информационной последовательности i на единичную матрицу порядка 3, входящую в состав матрицы G. Оставшиеся символы кодового слова (С4 - Сб) содержат проверочные символы (t^ - tz), полученные в результате умножения матрицы информационной последовательности на матрицу проверочных символов Р, также входящую в состав матрицы G.

Нетрудно проверить, что в случае (6, 3)-кода из примера 2.1.4 минимальное число ненулевых символов среди всех кодовых слов равно трем (кодовые слова 001101, 010011,100110 и 111000). Таким образом, d* = 3 и, согласно соотношению (2.5), код должен исправлять одну ошибку кодового слова. Как будет показано в следующем подпараграфе, это действительно так.