Скляр Б. Цифровая связь (2003) (1151859), страница 79
Текст из файла (страница 79)
(Турбокоды рассматриваются в разделе 8.4.) 6.4. Линейные блочные коды Линейные блочные коды (подобные коду, описанному в примере 6.2) — это класс кодов с контролем четности, которые можно описать парой чисел (и, 1) (обьяснение этой формы записи приводилось выше). В процессе кодирования блок из й символов сообщения (вектор сообщения) преобразуется в больший блок из и символов кодового слова (кодовый Главаб.
Канальное кодирование:часть 1 6.4.1. Векторные пространства Множество всех двоичных л-кортежей, У„, называется векторным пространством на двоичном поле двух элементов (О и 1). В двоичном поле определены две операции, сложение и умножение, причем результат этих операций принадлежит этому же множеству двух элементов. Арифметические операции сложения и умножения определяются согласно обычным правилам для алгебраического поля [4!. Например, в двоичном поле правила сложения и умножения будут следуюшими: Сложение ОЮО=О 09 ! =1 Умножение 0 0=0 0 1=0 1.0=0 1'1=1 1 ВО=1 1%1=0 Операция сложения, обозначаемая символом "9", — это та же операция сложения по модулю 2, которая описывалась в разделе 2.9.3. Суммирование двоичных л-кортежей всегда производится путем сложения по модулю 2.
Хотя для простоты мы чаше будем использовать для этой операции обычный знак ь. 6.4.2. Векторные подпространства Подмножество 5 векторного пространства !'„называется ладлрастранствам, если для него выполняются следуюшие условия. 1. Множеству 5 принадлежит нулевой вектор. 2. Сумма любых двух векторов в Я также принадлежит 5 (свайства замкнутости). При алгебраическом описании линейных блочных кодов даьшые свойства являются фундаментальными. Допустим, У, и У, — два кодовых слова (или кодовых вектора) в двоичном блочном коде (л, й). Код называется линейным тогда и только тогда, когда (Ъ; Э Уь) также является кодовым вектором.
Линейный блочный код — это такой код, в котором вектор, не принадлежаший подпространству, нельзя получить путем сложения любых кодовых слов, принадлежаших этому подпространству. Например, векторное пространство У4 состоит из следующих шестнадцати 4-кортежей: ~6.4. Линейные блочные коды 366 вектор), образованного с использованием элементов данного алфавита. Если алфавит состоит только из двух элементов (О и 1), код является двоичным и включает двоичные разряды (биты).
Если не будет оговорено противное, наше последуюшее обсуждение линейных блочных кодов будет подразумевать именно двоичные коды. х-битовьье сообшения формируют набор из 2' последовательностей сообшения, называемых ьг-кортежами (ь1-ьцр!е) (последовательностями ь! циФр). л-битовые блоки могут формировать 2" последовательности, также ильенуемые л-кортежами.
Процедура кодирования сопоставляет с каждым из 2" х-кортежей сообшения один из 2" лкортежей. Блочные коды представляют взаимно однозначное соответствие, в силу чего 2' х-кортежей сообшения однозначна отображаются в множество из 2" л-кортежей кодовых слов; отображение производится согласно таблице соответствия. Для линейных кодов преобразование отображения является, конечно же, линейным.
ОООО ООО1 ООЮ ООН ОЮО ОЮ1 ОНО О!11 1ООО ЮО) 1О)О Ю(1 ИОО 11О1 11!О Примером подмножества ттн являющегося подпространством, будет следующее: ОООО ОЮ1 1ОЮ Легко проверить, что сложение любых двух векторов подпространства может дать в итоге лишь один из векторов подпространства. Множество из 2' и-кортежей называется линейным блочным кодам тогда и только тогда, когда оно является подпространством векторного пространства тт„всех и-кортежей. На рис. б.)О показана простая геометрическая аналогия, представляющая структуру линейного блочного кода.
Векторное пространство тт„можно представить как составленное из 2" и-кортежей. Внутри этого векторного пространства существует подмножество из 2' п-кортежей, образующих надпространство. Эти 2' вектора или точки показаны разбросанными среди более многочисленных 2" точек, представляющих допустимые или возможные кодовые слова. Сообщение кодируется одним из 2" возможных векторов кода, после чего передается. Вследствие наличия в канале шума приниматься может измененное кодовое слово (один из 2" векторов пространства л-кортежей).
Если измененный вектор не слишком отличается (лежит на небольшом расстоянии) от действительного кодового слова, декодер может детектировать сообщение правильно. Основная задача выбора конкретной части кода подобна цели выбора семейства модулирующих сигналов, и в контексте рис. 6.10 ее можно определить следующим образом. 2" л-кортежей ° ссставллют полное пространство ел 2" и-кортежей секта валют надпространство кодовых слов Рис. б.)0. Структура линейного блочного кода 1.
Наполняя пространство тт„максимальным количеством кодовых слов, мы боремся за эффективность кодирования. Это равносильно утверждению, что мы хотим ввести лишь небольшую избыточность (нзбьпок полосы). 2. Мы хотим, чтобы кодовые слова были максимально удалены друг от друга, так что даже если векторы будут искажены в ходе передачи, их все еше можно будет с высокой вероятностью правильно декодировать. Глава 6. Канальное кодирование: часть! 6.4.3. Прииер линейного блочного кода (6, 3) Приведем необходимые предварительные замечания относительно кода (6, 3).
Он состоит из 2" = 2'= 8 векторов сообщений и, следовательно, восьми кодовых слов. В векторном пространстве Ч, имеется 2" (2' = шестьдесят четыре) б-кортежей. Нетрудно убедиться, что восемь кодовых слов, показанных в табл. 6.!„образуют в Ч, подпространство (ссть нулевой вектор, сумма любых двух кодовых слов дает кодовое слово этого же подпространства). Таким образом, эти кодовые слова представляют лилейлый блочлыа код, определенный в разделе 6.4.2. Может возникнуть естественный вопрос о соответствии кодовых слов и сообщений для этого кода (6, 3). Однозначного соответствия для отдельных кодов (л, 1) не существует; хотя, впрочем, здесь нет полной свободы выбора.
Подробнее о требованиях и ограничениях, сопровождающих разработку кода, будет рассказано в разделе 6.6.3. Таблица 6.1. Соответствие кодовых слов и сообщений Вектор сообшевяя Кодовое слово 000 !00 010 1!О 00! 101 011 1!! 000000 !10100 О!1010 101!10 1О!00! 011101 110011 00011! 6.4.4. Матрица генератора ()=ш, Ч! ь Ч +...+ Ч„. Здесыи, = (О или 1) — цифры сообщения, а)= 1, ...,/г. 6.4. Линейные блочные коды При больших !г реализация таблицы соответствия кодера становится слишком громоздкой. Для кода (127, 92) существует 2" или приблизительно 5 х 1Оз" кодовых векторов.
Если кодирование выполняется с помощью простой таблицы соответствия, то представьте, какое количество памяти нужно лля такого огромного числа кодовых слов! К счастью, задачу можно значительно упростить, по мере необходимости генерируя необходимые кодовые слова, вместо того чтобы хранить их в памяти постоянно. Поскольку множество кодовых слов, составляющих линейный блочный код, является /с-мерным подпространсгвом л-мерного двоичного векторного пространства (й< л), всегда можно найти такое множество л-кортсжей (с числом элементов, меньшим 2"), которое может генерировать все 2' кодовых слова подпространства.
О генерирующем множестве векторов говорят, что оно охватывает подпространство. Наименьшее шнейпо незавасимое множество, охватывающее подпространспю, называется базисам подпространства, а число векторов в этом базисном множестве является размерностью подпросгранстаа. Любое базисное множество !г линейно независимых и-коРтежей Чь Чь ..., Чг можно использовать для генерации нужных векторов линейного блочного кода, поскольку каждый вектор кода ЯвлаетсЯ линейной комбинацией Чь Чь „,, Чо Иными словами, каждое из множества 2" кодовых слов (Щ можно представить следующим образом: ора можно определить как массив размером н х н: Ч~ Чз гн У21 Узз У за (6.24) Ч„, редставлять векторами-строками.
Таким образом, сооб- ть 1 бит сообшения) представляется как вектор-строка рока и х столбцов): ш =то ни, ..., т„. кодового слова 1) будет выглядеть как произведение ш и С: (6.25) выполняется по следующему правилу: с, = ) анйь 1=1,...,1 1'=1,...,т. Здесь А — матрица размером 1хн,  — матрица размером и хин а результируюшая матрица С имеет размер! х т. Для примера, рассмотренного в предыдушем разделе, матрица генератора имеет следующий вид: 1 0 1 0 0 0 1 1 О 1 0 . 1 0 1 0 0 1 (6.26) Ч, Чз 1 Ч! "~" 1' Ч~ "~" 0 Ч3 Чз 110100+011010+000000= 1 0 1 1 1 О (кодовое слово для вектора сообщения 1 1 0) Таким образом, кодовый вектор, соответствуюший вектору сообщения, является линейной комбинацией строк матрицы С. Поскольку код полностью определяется матрицей С, кодеру нужно помнить лишь й строк матрицы С, а нс все 2" кодовых вектора.
Из приведенного примера можно видеть, что матрица генератора размерностью 3 х 6, приведенная в уравнении (6.26), полностью заменяет исходный массив кодовых слов размерностью 8 х 6, приведенный в табл. 6.1, что значительно упрошает систему. Глава б.
Канальное кодирование: часть 1 358 Здесь Ч„Ч. и Чз — три линейно независимых вектора (подмножество восьми кодовых векторов), которые могут сгенерировать все кодовые векторы. Отметим, что сумма любых двух генерирующих векторов в результате не даст ни одного генсрируюшего вектора (противоположность свойству замкнутости). Покажем, как с использованием матрицы генератора, приведенной в выражении (6.26), генерируется кодовое слово (), для четвертого вектора сообшения 110 в табл. 6.1: 6.4.5. Систематические линейные блочные коды Р 1» (6.27) Р>> Ргг "' Рилн рн р„- рчл Ю р„р»г " рмл „> Здесь Р— массив четности, входящий в матрицу генератора, ри =(О или 1), а 1»вЂ” единичная матрица размерностью тт х Ф (у которой диагональные элементы равны 1, а все остальные — О).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
