Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Лекции 14. Линейные коды: спектры, двойственность.

Линейные коды.

Наложим на множество C  ограничение, превратим его из подмножества в  подпространство Bn.

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

Определение. Код C Bn называется  линейным (групповым), если для любых α, β C: α + β C.

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

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

В случае двоичного кода: Bn – линейное пространство; зададим в нем подмножество векторов C Bn, и для любых α, β C: α + β C. Отсюда следует, что вместе с любым набором вектров линейному коду принадлежит их линейная комбинация, поэтому C – подпространство Bn.

Пусть dimC = k, | C | = 2 k. Согласно определению: C – групповой код.

Легко показать, что d (c) = min | α | (α С, α 0).

Для любого линейного кода существуют 2 матрицы: G – порождающая, H – проверочная.

                  

Порождающая матрица состоит из векторов (записанных в строке покомпонентно) некоторого базиса подпространства C. Для любого β C: β – линейная комбинация строк G. Если dimC = k, то G должна содержать k строк.

Проверочная матрица кода C – это такая матрица, что для любого α С:

α HT = 0.

При построении кода (алгоритмов кодирования и декодирования) C чаще используется матрица H.

Определение. Код С* Bn называется ортогональным C, если для любых α, β: α С*, β С выполняется условие: αβ = 0.

Из курса линейной алгебры известно, что если dimC = k, то dimC* = nk. При этом порождающей матрицей H * кода С*  является проверочная матрица H кода С. (И наоборот.)

Пример. Код с проверкой на четность.

dimC = n – 1, dimH = 1, H = (11…1)1x n

Рассмотрим теперь операции преобразования кодовых матриц.

Элементарные преобразования матриц:

1) Перемена местами строк.

2) Умножение строки на число.

3) Сложение строки с линейной комбинацией других строк.

4) Перемена столбцов местами.

Определение. Коды C и D называются эквивалентными, если G (C) можно получить из G (D) с помощью элементарных преобразований.

Утверждение. Для любого С существует эквивалентный код С’ такой, что

  (14.1)

Определение. Код с порождающей матрицей вида (14.1) называется систематическим.

В таком коде в подматрице  находятся информационные столбцы, в  - проверочные столбцы.

Проверочных символов (nk). В H (C’) (nk) строк, каждая строка – соотношение, задающее линейную комбинацию: 1-я – 10…0, 2-я – 01…0 и т.д.

Пример.

n = 5, k = 3 и

           

Пусть α 1, α 2, α 3 – информационные символы, α 4, α 5 – проверочные. Тогда проверочные соотношения:

Алгоритм кодирования осуществляется следующим образом: любая строка H дает проверочную комбинацию. Так мы преобразуем слова из Bk, подлежащие передаче, просто добавляя к ним n-k символов – результаты проверочных соотношений после подстановки туда информационных символов.

  Заметим, что в нашем примере мы получили код с d (C) = 2.

В общем случае для декодирования с помощью таблицы декодирования на декодере хранится и в процессе алгоритма декодирования обрабатывается таблица, содержащая  n2n символов (2n векторов). Вы уже знаете, насколько сложно работать с экспоненциальным объемом информации.

Свойство линейности кода позволяет в этом вопросе получить существенную выгоду. Для хранения таблица декодирования нужно хранить ее первую строку и первый столбец, т.е. 2n-k+2k векторов. Это следует из того, что линейный код Bk – это подгруппа абелевой группы Bn.

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

Для линейных кодов такой алгоритм декодирования  называется декодированием с помощью «стандартной расстановки».

Определение. Синдром линейного кода  называется вектор Sα = α HT.

Если проверочная матрица имеет (n — k) строк, то синдром Sy произвольного вектора у  из B n является вектором длины (n — k).

Поскольку по определению линейного кода вектор у является кодовым тогда и только тогда, когда yHT = 0, то справедливо следующее утверждение.

Утверждение. Синдром Sy вектора у равен 0 тогда и только тогда, когда у является кодовым вектором.

Утверждение. Для двоичного линейного кода синдром Sy принятого вектора у равен сумме тех столбцов проверочной матрицы H, где произошли ошибки.

Утверждение. Пусть U – кодовое слово,при передаче из него получено слово V= U + e, где вектор e – вектор ошибки. Алгоритм на основе стандартной расстановки правильно декодирует слово тогда и только тогда, когда вектор ошибки – образующая смежного класса.

Оно вытекает из следующего утверждения.

Утверждение. Два вектора u и v принадлежат одному и тому же смеж­ному классу тогда и только тогда, когда их синдромы равны.

Достаточно важным для линейных кодов является следующее простое утверждение.

Теорема 14.1.     Кодовое расстояние линейного кода d (C) = d, тогда и только тогда, когда любые (d – 1) столбцов H линейно-независимы и данное d является максимально возможным.

Спектр кода.

Существует еще одна важная характеристика кода – это спектр кода.

Рассмотрим код V = (v 1vk). Пусть для кодового слова vi величина rs (vi) – это число кодовых слов таких, что ρ (vj, vi) = s. Тогда вектору vi сопоставляется (r 0(vi)… rk (vi)) – спектр vi – кода. А спектры всех кодовых точек можно задавать в виде таблицы размером (k+1)xk.

Если V – линейный код, то спектры всех vi одинаковые. Поэтому для линейного кода спектром называется вектор (a 0an), т.е. число кодовых слов весов 0… n.

Важным инструментом использования спектра является теорема Маквильямс.

Теорема 14.2. (Маквильямс).

Пусть есть код V и его спектр (a 0an) и код ортогональный V * и его спектр (b 0bn), тогда справедливо соотношение , где z – переменная.

Мы здесь даем саму теорему без доказательства.

Эта теорема дает возможность выражать спектр кода через спектр ортогонального кода.

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

Следствие1. Пусть . Тогда справедливо соотношение

.

Доказательство. Так как , то из

с использованием теоремы Маквильмс получаем

.

Приравнивая коэффициенты при одинаковых степенях, имеем

.

Следствие доказано.

Заметим, что из  следует, что

.

Следствие 2. Справедливо соотношение

, где  - число точек Bn веса s на расстоянии r от некоторой точки кода.

Пусть C (s) – число точек Bn веса s, попавших в шар радиуса t линейного кода, исправляющего t ошибок.

Следствие 3. Справедливо соотношение:

.

Ниже мы приведем пример использования этих соотношений.

Упражнения.

1. Пусть G – произвольный -код, точки которого выписаны в матрицу A размером . Показать, что каждый ненулевой столбец A содержит ровно  единиц.

2. Пусть G – произвольный -код. Доказать следующие неравенства:

a) ;

b) .

3.Доказать следующие «общие» свойства функции

4*.Доказать, что при n≥2d-1 число проверочных символов, необходимое для того, чтобы минимальный вес линейного кода с n символами достигал значения d, равно, самое меньшее, 2d- log d-2.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...