У. Питерсон - Коды, исправляющие ошибки (1267328), страница 14
Текст из файла (страница 14)
Наиболее интересный класс древовидных линейных кодов, называемых свергочмьиии или рекурренгными кодами, получается, если в качестве матриц Г; взять сдвиги матрицы Гь Точнее, матрица Г, получается в результате смещения вправо матрицы Г, на Ьа мест и заполнения оставшихся слева Ьз мест нулями. Большннство подробно изученных древовидных кодов является кодами этого типа, и поэтому только такие сверточпые древовидные коды будут рассматриваться в остальной части этой книги. Пример.
Двоичный древовидный код, используемый в примерах первой главы, является в действительности сверточным ко- Порождающая матрица этого кода !!О! !!О! !!О1 (З.П) (Всюду в этой книге подразумевается, что на незаполненных местах матриц такого типа стоят нули.) Кодовой последовательностью, соответствующей информационной последовательности 1= 1 О 1 1 О ..., является последовательность ! б = — 1 1 О 1 1 1 1 О О 1 ...
(ср. равд. 1 5). В любых реальных кодере и декодере может содержаться только конечное число символов кода; предположим, что через и обозначено число символов, хранящихся в декодере. Совокупность кодовых слов длины и, обрабатываемых прн декодировании первых по символов кодового блока, образует группу по сложению и, следовательно, линейное подпространство в пространстве всех наборов длины и. Порождающая матрица этого пространства представляет собой матрицу порядка А Хп, занимающую верхний левый угол матрицы б. Матрица б может быть представлена в виде б бо~-2 б -з бо б! б2 бо б1 бо (3.12) бо б~ бо где все матрицы б, состоят из йо строк и по столбцов.
В качестве матрицы бо всегда выбирается матрица ранга йо., следовательно, ранг матрицы б равен й = вайо. Пространство строк матрицы б вида (3.!2) называется сеергочным (п,й)-кодом. Верхние йо строк матрицы б образуют базисную порондаюи(ую матрицу кода. Пример. Пусть в предыдущем примере и = 4.
Порождающая матрица для совокупности первых кодовых слов в этом (4,2)-коде б=(ОО! !1' Вели и первый блок декодирован правильно, то можно устранить его влияние при последующем декодировании. Таким образом„ каждый блок можно рассматривать как первый при условии, что все предыдущие блоки декодированы правильно. Влияние предыдущих блоков на кодовые слова в фнксированяом узле заключается просто в прибавлении определенного набора символов к каждому из них. Этот набор не влияет на способность кода исправлять ошибки и поэтому может не учитываться. Для такого декодирования с обратной связью (как его называют) совокупность кодовых слов длины и, выходящих из каждого узла дерева, является пространством строк матрицы б, определяемой равенством (3.12) . Очень важен вопрос о том, что произойдет, если при декодировании появится ошибка.
Поскольку в этом случае обратная информация, предназначенная для модификации совокупности кодовых слов, некорректна, то правдоподобно возникновение ошибок и при дальнейшем декодировании. Этот эффект размножения ошибок, который обсуждается в гл. 13, может быть устранен путем применения дефинитного декодирования (без обратной связи).
Однако в большинстве случаев прн рассмотрснии сверточных кодов предполагается использование декодирования с обратной связью, и поэтому, за исключением нескольких важных частных случаев, рассмотренных в гл. 13, основное внимание в этой книге уделяется декодированию с обратной связью. Ббльшая часть результатов, выведенных в предыдущем разделе для линейных блоковых кодов, применима к пространству строк матрицы б вида (3.12). В частности, минимальный вес кодовых слов, не все первые пь символов которых равны нулю, равен минимальному расстоянию й кода. Далее, код можно описывать как нулевое пространство матрицы Н ранга и — й. Каждая из и — й (линейно независимых) строк матрицы Н определяет обобщенные проверки на четность некоторой совокупности символов в каждом кодовом слове. Пример.
Для кода из предыдущего примера ~11Об~ Это значит, что сумма первых двух символов и сумма первого, третьего и четвертого символов каждого кодового слова должны быть равны нулю. Далее, теорема 3.1 верна для матрицы Н. Однако ее следствие должно быть модифицировано и выглядит теперь следующим образом: Следствие 3.2. Код, являюи(ийся нулевым пространством матрицы Н, имеет минимальный вес, равный самое меньшее ш, тогда и только тогда, когда любая совокупность ш — 1 или меньшего „исла столбцов матрицы Н, для которой хотя бы один ее столбец ыбирается среди нервых яо столбцов, является линейно независимой.
рак же как для линейных блоковых кодов, любая порождающая матрица сверточного кода комбинаторно-эквивалентна некоторой матрице в ступенчатой канонической форме 1Ро ОР, ... ОР 1Р ... ОР (3.13) Здесь Р~ — произвольная матрица размерности Ао~((по — йо), а ! и Π— соответственно единичная и нулевая матрицы порядка яо.
Первые йо символов в каждом блоке кодового слова длины яо для кода, порождаемого матрицей б вида (3.13), являются информационяыми символами, а последние по — Ао символов — проверочными символами. Коды этого типа называются систематическими. Поскольку ранг матрицы бо равен А„то теорема 3.2 верна для сверточных кодов так же, как и для блоковых кодов. Другими словами, любой сверточный код эквивалентен систематическому сверточному коду. (Эквивалентный сверточный код получается в результате перестановки столбцов только внутри блоков длины ио, причем во всех блоках производятся одни и те же перестановки.) Пример.
Рассмотренный в предыдуших примерах код представлен в форме систематического. Поскольку йо= но — йо = 1, то матрицы Р; являются просто двоичными символами, а именно Ро= Р1=Щ. Пример. Систематический сверточный (12,6)-код с порождающей матрицей б порождается также (в несистематической форме! матрицей б' и эквивалентен коду с порождающей матрицей б"~, где 11 01 01 00 01 01 11 01 01 00 01 11 01 01 00 11 01 01 11 01 11 оо оооо оо 11 ОО 10 11 !! 10 11 оо оо— оо оо 11 ОО 01 1! 11 01 11 11 1О 11 00 11 1О ! 1 11 !О 1! 11 01 11 ОО 11 01 11 11 01 11 С» Относительно последнего кода говорят, что длина кодового ограничения для этого кода равна 6 битам; этот вопрос обсуждается в гл.
13. По аналогии с теоремой 3.3 для блоковых кодов для сверточных кодов справедлив следующий результат: 'Теорема 3.4. Пространство строк матрицы С в форме (3.13) является нулевым пространством матрицы т Рт|0 Рлю( (3.14) РУД 1О РШ-20 ... Р01 Соотношение (3.14) весьма наглядно отражает основную структуру сверточных кодов. Рассмотрим двоичный код при условии, что и,— ял — — 1; тогда каждая из матриц Р; представляет собой т двоичный вектор-строку длины пл — 1. Нижние пл — кл строк матрицы Н, которые образуют базисную проверочную матрицу кода, таковы, что проверочные символы некоторого блока представляют собой сумму тех информационных символов этого блока, которые соответствуют единицам в матрице Рл сумму тех информационных символов в первом предшествующем блоке, которые соответт ствуют единицам в матрице Р~, ..., и сумму тех информацион- Доказательство.
Сумма рангов матриц С н Н равна и. Утверждение теоремы вытекает из того факта, что СНт = О. Ч. т.д. ~ых символов в (тп — 1)-м предшествующем блоке, которые соотных т ветствуют единицам в матрице Р .о В силу ограничения, налоенного на сверточные коды, проверочные символы в каждом блоке являются суммой информационных символов, находящихся относительяо друг друга на одних и тех же позициях. Верхняя строка матрицы Н иллюстрирует тот факт, что, хотя проверочные ~имволы в крайнем левом блоке первоначально использовались для проверки информационных символов в других блоках, влияние этих символов исключалось, поскольку они уже были декодированы и тем самым предположительно известны на декодере.
Эти идеи очевидным образом обобщаются на случай и, — йь чь 1. 8.4. Стандартное расположение Пусть )т — линейный (и, й)-код, г1 — нулевой вектор и Ль Ьм ... ..., Ь ь — остальные кодовые векторы. Тогда таблицу декодировао ния можно составить следующим образом. Кодовые векторы располагаются в виде строки с нулевым вектором слева. Затем один из оставшихся наборов длины п, например дь помещается под нулевым вектором. (Обычно это бывает один из наборов, которые наиболее вероятно получить на выходе, если по каналу передавался нулевой вектор.) Далее строка заполняется так, чтобы под каждым кодовым вектором Ь; помешался вектор и, + йь Аналогично в первый столбец второй строки помещается вектор пг и строка заполняется таким же способом. Процесс продолжается до тех пор, пока каждый возможный набор длины и не появится где-нибудь в таблице.
Это стандартное расположение, конечно, в точности совпадает с таблицей смежных классов, описанной в гл. 2. Строки являются смежными классами, а векторы в первом столбце — образующими смежных классов.. Стандартное расположение полезно прн анализе и блоковых, и сверточных кодов. Ниже доказывается несколько результатов, относящихся к стандартному расположению для блоковых кодов. В последующем обсуждении полученные результаты модифицируются настолько, насколько это необходимо, для того чтобы охватить и случай сверточных кодов. Если передавался вектор и, а получен вектор ч, то ч — и называется набором ошибок. Теорема 3.5.
Если стандартное расположение используется как таблица декодирования для блокового кода, то по полученному вектору э будет правильно декодирован переданный вектор и тогда и только тогда, когда набор ошибок э — и является образуюи1им смежного класса. Доказательство, Если э — ц = яь где и; — образующий рго смежного класса, то вектор ч = и;+ и должен находиться в стандартном расположении в с-и смежном классе под кодовым словом ц и поэтому будет правильно декодирован. Если же вектор ч — и не является образующим смежного класса, то вектор ч должея находиться в некотором смежном классе, например )чм, с обРазУющнм Яь Тогда вектоР ч Расположен в )чй стРоке, но не под вектором и, потому что ч М вс+ ц. Ч. т.
д. Предположим, что линейный код является нулевым пространством матрицы Н размерности (и — й)Хп. Для любого полученного на выходе вектора ч вектор 8 = чНт с и — й-компонентами называется синдромом. Поскольку рассматриваемый код — это нулевое пространство матрицы Н, то некоторый вектор является кодовым словом тогда и только тогда, когда его синдром равен нулю. Вообще каждой строке матрицы соответствует проверочное соотношение, которому должны удовлетворять кодовые слова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
