Понеаснни. Моделирование систем связи в matlab
Скачать 2.78 Mb.
|
Пример. Рассмотрим код (7, 4) с порождающим многочленом Р(Х)= X 3 +X 2 + 1. Имеем 7 = 2 3 – 1, следовательно с помощью этого кода можно исправить все 1-битовые ошибки. В табл. 3.2, а приводятся все используемые кодовые слова. Отметим, что d min = 3, значит, данный код – это код с коррекцией 1-битовых ошибок. Например, для блока данных 1010 имеем D(X)= X 3 +X и X n-k D(X) = X 6 + X 4 . Деление выполняется согласно правилам деления полиномов 2 6 D(X) X 6 + + X 4 X 6 + X 5 + X 3 X 5 + X 4 + X 3 X 5 + X 4 + X 2 X 3 + X 2 X 3 + X 2 + 1 1 X 3 + X 2 + 1 P(X) X 3 + X 2 + 1 Q(X) R(X) Рис. 4.9 Получение остатка от деления на порождающий полином Рисунок 2.10 – Получение остатка от деления на порождающий полином 54 Для коррекции ошибок требуется таблица синдромов, показанная в табл. 3.2, б. Например, для последовательности ошибок 1000000 Е(Х)будет равно Х 6 Z(X) X 6 X 6 + X 5 + X 3 X 5 + + X 3 X 5 + X 4 + X 2 X 4 + X 3 + X 2 X 4 + X 3 + X X 2 + X X 3 + X 2 + 1 P(X) X 3 + X 2 + 1 Q(X) + B(X) S(X) Рис. 4.10 Получение синдрома ошибки Рисунок 2.11 – Получение синдрома ошибки Таким образом, S = 110. Остальные ячейки табл. 3.2, б вычисляются аналогично. Теперь предположим, что был получен блок 1101101, или Z(X) = X 6 + X 5 + X 3 + X 2 + 1. Z(X) X 6 + X 5 + X 3 + X 2 + 1 X 6 + X 5 + X 3 X 2 + 1 X 3 + X 2 + 1 P(X) X 3 + X 2 + 1 B(X) S(X) Рис. 4. 11 Получение синдрома из Z(X) Рисунок 2.12 – Получение синдрома из Z(X) Следовательно, S = 101. Используя табл. 3.2, б, получаем Е = 0001000. Тогда Т = 1101101 0001000 = 1100101 Итак, согласно табл. 3.2, а, был передан блок данных 1100. Таблица 3.3 – Циклический код с коррекцией 1-битовых ошибок (7,4) а) Таблица используемых кодовых слов Блок данных Кодовое слово 1 2 0000 0000000 0001 0001101 0010 0010111 0011 0001010 55 Продолжение таблицы 3.3 0100 0100011 0101 0101110 0110 0110100 0111 0111001 1000 1000110 1001 1001011 1010 1010001 1011 1011100 1100 1100101 1101 1101000 1110 1110010 1111 1111111 б) Таблица синдромов, соответствующих 1-битовым ошибкам Ошибочная комбинация Синдром 0000001 001 0000010 010 0000100 100 0001000 101 0010000 111 0100000 011 1000000 110 Коды БХЧ Коды БХЧ являются одним из наиболее мощных циклических блочных кодов и получили широкое применение в беспроводных приложениях. Для любой пары положительных целых чисел т и t существуют двоичные коды БХЧ (n, k)со следующими параметрами Длина блока n = 2 m - 1 Количество контрольных битов n – k ≤ mt Минимальное расстояние d min ≥ 2t + 1 С помощью такого кода можно исправить все слова, содержащие t (или менее) ошибок. Порождающий многочлен кода БХЧ можно создать из множителей полинома (Х 2m-1 + 1). Использование кодов БХЧ предоставляет некоторую свободу выбора параметров (длина блока, степень кодирования). Коды БХЧ очень важны, поскольку при блоках, длина которых равна порядка несколько сотен, коды БХЧ превосходят своими качествами другие 56 блочные коды с той же длиной блока и степенью кодирования. В наиболее часто применяемых кодах БХЧ используется двоичный алфавит и блок кодового слова длиной n = 2 т - 1, где т = 3,4, ... В таблице 3.4 перечислены параметры БЧХ для кодов длиной до 2 8 – 1. В таблице 3.5 приводятся некоторые порождающие многочлены БЧХ. Таблица 3.4 – Параметры кодов БЧХ n k t n k t n k t n k t n k t 7 4 1 63 30 6 127 64 10 255 207 6 255 99 23 15 11 1 24 7 57 11 199 7 91 25 7 2 18 10 50 13 191 8 87 26 5 3 16 11 43 14 187 9 79 27 31 26 1 10 13 36 15 179 10 71 29 21 2 7 15 29 21 171 11 63 30 16 3 127 120 1 22 23 163 12 55 31 11 5 113 2 15 27 155 13 47 42 63 6 7 106 3 8 31 147 14 45 43 57 1 99 4 255 247 1 139 15 37 45 51 2 92 5 239 2 131 18 29 47 45 3 85 6 231 3 123 19 21 55 39 4 78 7 223 4 115 21 13 59 36 5 71 9 215 5 107 22 9 63 Таблица 3.5 – Порождающие полиномы кодов БЧХ n k t P(X) 7 4 1 X 3 + X + 1 15 11 1 X 4 + X + 1 15 7 2 X 8 + X 7 + X 6 + X 4 + 1 15 5 3 X 10 + X 8 + X 5 + X 4 + X 2 + X + 1 31 26 1 X 5 + X 2 + 1 31 21 2 X 10 + X 9 + X 8 + X 6 + X 5 + X 3 + 1 Для декодирования сигналов БХЧ было разработано большое количеств методов, требующих меньше памяти, чем прямой поиск в таблице. Идея одной из наиболее простых схем стоит в вычислении полинома локализации ошибки с последующим нахождением его корней. Сложность данного алгоритма увеличивается как квадрат количества ошибок, которые нужно исправить. Коды Рида-Соломона Коды Рида-Соломона (Reed-Solomon codes – RS codes) – это широко используемый подкласс недвоичных кодов БХЧ. При использовании кодов 57 Рида-Соломона данные обрабатываются порциями по m бит, именуемыми символами. Код (n, k) характеризуется следующими параметрами Длина символа m бит Длина блока n = (2 m – 1) символов = m(2 m – 1) бит Длина блока данных k символов Размер контрольного кода n - k = 2t символов = m(2t) бит Минимальное расстояние d min = (2t + 1) символов Таким образом, алгоритм кодирования расширяет блок k символов до размера n, добавляя (n-k) избыточных контрольных символов. Как правило, mявляется степенью 2; широко используется значение т = 8. Пример. Пусть t =1, т =2. Обозначая символы как 0, 1, 2, 3, их двоичные эквиваленты можно записать как 0 = 00; 1 = 01; 2 = 10; 3 = 11. Код имеет следующие параметры: n = 2 2 – 1 = 3 символа = 6 бит, n - k = 2 символа = 4 бит. С помощью данного кода можно исправить любой пакет ошибок, который искажает 2-битовый символ. Коды Рида-Соломона удобны для исправления пакетов ошибок. Данный тип кодов характеризуется высокоэффективным использованием избыточности, длина блоков и размеры символов могут легко приспосабливаться под сообщения разных размеров. Кроме того, для таких кодов существуют эффективные методы декодирования [2]. Известные блочные коды На рисунке 2.13 приведены графики зависимости вероятности ошибки в декодированном бите от вероятности ошибки в канальном символе, по которым сравниваются разные блочные коды. Для кодов Хэмминга на графике взяты значения m = 3, 4 и 5 или (n, k) = (7,4), (15,11), (31,26). Для описания гауссового канала с использованием когерентной демодуляции сигналов BPSK, вероятность ошибки в канальном символе можно выразить через E c /N 0 : 0 2 с E p Q N (3.31) 58 Здесь E с /N 0 – отношение энергии кодового символа к. Чтобы связать E с /N 0 сотношением энергии бита информации к спектральной плотности мощности шума (E b /N 0 ), используем следующее выражение 0 0 , c b E k E N n N (3.32) Рисунок 2.13 – Зависимость вероятности битовой ошибки от вероятности ошибки в канальном символе для нескольких блочных кодов Для кодов Хэмминга уравнение принимает следующий вид: 0 0 2 1 , 2 1 m c b m E m E N N (3.33) 59 Объединяя уравнения (3.32) и (3.33), вероятность ошибки Р В при когерентной демодуляции сигналов BPSK в гауссовом канале можно выразить как функцию E b /N 0 . Результаты для различных типов блочных кодов отображены на рисунок 2.14. Для кодов Хэмминга взяты следующие значения (n, k) = (7,4), (15, 11), (31, 26). Рисунок 2.14 – Зависимость Р В от E b /N 0 при когерентной демодуляции сигналов BPSK в гауссовом канале для нескольких блочных кодов На рисунке 2.15 показаны расчетные характеристики кодов БХЧ для когерентно демодулированного сигнала BPSK с жестким и мягким декодированием. Мягкое декодирование для блочных кодов не применяется из-за своей сложности, хотя оно и дает увеличение эффективности кодирования порядка 2 дБ по сравнению с жестким декодированием. При данной степени кодирования вероятность ошибки при декодировании уменьшается с ростом длины блока n. Таким образом, при данной степени кодирования интересно рассмотреть необходимую длину блока для 60 сравнения характеристик жесткого и мягкого декодирования. Из рисунка видно, что при фиксированной степени кодирования и жестком декодировании кода БХЧ длиной 8n или более наблюдаются лучшие характеристики, чем при мягком декодировании кода БХЧ длиной n. Существует специальный подкласс кодов БХЧ (которые были разработаны раньше кодов БХЧ), который является недвоичным набором, это коды Рида- Соломона (Reed-Solomon code). Рисунок 2.15 – Зависимость Р В от E b /N 0 для когерентно демодулируемого сигнала BPSK в гауссовом канале с использованием кодов БХЧ На рисунок 2.16 показана зависимость Р B от вероятности появления ошибки в канальном символе р, полученная из уравнений для различных ортогональных 32-ричных кодов Рида-Соломона с возможностью коррекции t ошибочных бит в символе и n = 31 (тридцать один 5-битовый символ в кодовом блоке). На рис 2.17 показана зависимость Р B от E b /N 0 для таких систем кодирования при использовании модуляции MFSK и некогерентной 61 демодуляции в канале с AWGN. Для кодов Рида-Соломона вероятность появления ошибок является убывающей степенной функцией длины блока, n, а сложность декодирования пропорциональна небольшой степени длины блока. Иногда коды Рида-Соломона применяются в каскадных схемах. В таких системах внутренний сверточный декодер сначала осуществляет некоторую защиту от ошибок за счет мягкой схемы решений на выходе демодулятора; затем сверточный декодер передает данные, оформленные согласно жесткой схеме, на внешний декодер Рида-Соломона, что снижает вероятность появления ошибок [3]. Рисунок 2.16 – Зависимость P B от р для различных ортогональных 32-ричных кодов Рида-Соломона с возможностью коррекции t бит в символе и n = 31 2.4.1 Сверточные коды Блочные коды являются одной из двух категорий кодов с коррекцией ошибок, широко используемых при беспроводной передаче. Вторая категория – это сверточные коды. Блочный код (n, k)обрабатывает данные блоками по k бит, генерируя на выходе блок из nбит (n > k)для каждого n- битового блока на входе. Если прием и передача данных происходят относительно непрерывным потоком, то блочный код (в частности, с большим значением n)может быть не так удобен, как код, который генерирует избыточные биты непрерывно. В последнем случае обнаружение 62 и исправление ошибок выполняется непрерывно, и именно в этом состоит преимущество сверточных кодов. Рисунок 2.17 – Зависимость P В от E b /N 0 для различных ортогональных кодов Рида-Соломона с возможностью коррекции t бит в символе и n = 31, при 32-ричной модуляции MFSK в канале AWGN Сверточный код задается тремя параметрами: n, k и К. Код (n, k, K) обрабатывает входящие данные порциями по k бит и генерирует выходную последовательность, состоящую из n бит для каждых k бит входа. До этого момента принципы работы сверточных и блочных кодов не отличаются. Для сверточных кодов n и k, как правило, являются очень малыми числами. Разница между двумя типами кодов состоит в том, что сверточные коды используют память, которая характеризуется длиной кодового ограничения К. По сути, текущая n-битовая выходная последовательность кода (n, k, К) зависит не только от значений текущего входного блока, состоящего из k бит, но также и от предыдущих (К - 1) k-битовых блоков. Следовательно, текущая выходная n-битовая последовательность является функцией последних (K k)входных битов. Принципы работы сверточных кодов удобно рассмотреть на конкретном примере, представленном на рисунок 2.18. Здесь приведены два 63 альтернативных представления кода. Рисунок 2.18, а – это регистр сдвига, который наиболее удобен для описания и реализации процесса кодирования. Рисунок 2.18, б – это эквивалентное представление, удобное для изучения процесса декодирования. Для кода (n, k, К)регистр сдвига содержит последние (K k)входных битов; в исходном состоянии все ячейки регистра содержат нули. Кодер генерирует n выходных битов, после чего наиболее "старые" k бит регистра стираются и вводится новая k-битовая последовательность. Хотя выходные n бит зависят от (K k)входных битов, степень кодирования равна отношению k входных битов к n выходных битов. Следовательно, как и для блочного кода, степень кодирования равна k/n. Наиболее широко используемые двоичные кодеры имеют k = 1; соответственно, длина регистра такого кодера равна К. В рассматриваемом примере (рисунок 2.18, а) используется код (2, 1, 3). Здесь кодер преобразует входной бит u n в два выходных бита – v n1 и v n2 , используя три последних полученных бита. Первый сгенерированный бит поступает из верхнего логического контура (v n1 = u n u n-1 u n-2 ) а второй – из нижнего (v n2 = u n u n-2 ). Для любого данного k-битового входа существует 2 k(K-1) различных функций, отображающих k входных битов в n выходных. Решение о том, какая из этих функций будет использована, зависит от истории последних (К – 1) k-битовых входных блоков. Следовательно, сверточный код можно представить как конечный автомат. Автомат имеет 2 k(K-1) различных состояний, переход между которыми определяется последними k входными битами и дает n выходных битов. Начальное состояние автомата – все нули. Для примера приведенного на рисунок 2.18, б существует 4 состояния, по одному для каждой возможной комбинации последних двух битов. Следующий входной бит инициирует переход и дает два выходных бита. Например, если последние два бита — 10 (u n-1 = 1; u n-2 = 0), а следующий бит равен 1 (u n = 1), то текущим состоянием будет b(10), а следующим состоянием – d(11). Выход имеет такой вид v n1 = u n-2 u n-1 u n = 0 1 1 = 0 v n2 = 0 1 = 1 2.4.3.1 Декодирование Чтобы описать процесс декодирования, можно расширить диаграмму состояний, показав в кодере хронологическую последовательность битов. Если диаграмма состояний расположена вертикально, как на рисунок 2.18, б, то расширенная диаграмма называемая решетчатой, строится путем воспроизведения состояний и представления переходов между состояниями в 64 горизонтальном направлении слева направо, в соответствии с течением времени или посредством ввода данных (рисунок 2.19). Рисунок 2.18 – Сверточный кодер (2, 1, 3) Если длина кодового ограничения К велика, то решетчатая диаграмма будет слишком громоздкой. В таком случае для отображения переходов можно использовать 2 K-2 упрощенных решетчатых фрагментов. На рисунок 2.20 приводится подобное отображение для кода (2, 1, 7). Здесь показано каждое состояние кодера и даны определения всех ветвей диаграммы. Состояние a = 00 b = 10 c = 01 d = 11 t 1 t 2 t 3 t 4 t 5 t 6 00 00 00 00 00 11 11 11 10 01 01 01 10 00 11 11 10 01 10 10 10 00 11 01 11 10 01 11 00 01 Ветвь кодового слова Условные обозначения: Входной бит 0 Входной бит 1 Рис. 5.6 Решетчатая диаграмма сверточного кодера (2, 1, 3) Рисунок 2.19 – Решетчатая диаграмма для кодера, изображенного на рисунке 2.18 U n U n-1 U n-2 Входные биты Выходные биты v n1 = U n-2 U n-1 U n v n2 = U n-2 U n а) Регистр сдвига кодера a=00 b=10 c=01 d=11 00 11 00 10 01 01 10 11 Выходные биты Состояние кодера Входной бит = 0 Выходной бит = 1 б) Диаграмма состояний коде- ра 65 Рисунок 2.20 – Решетчатые диаграммы для кодера (2, 1, 7) Любая корректная выходная последовательность определяется маршрутом в решетчатой диаграмме. Для рассматриваемого примера 1 2 3 4 5 6 7 Входные биты Выходные биты а) Диаграмма регистра сдвига А В 2 1 3 33 00 11 10 01 0 0 1 32 00 11 10 01 4 2 5 34 00 11 10 01 6 3 7 35 00 11 10 01 8 4 9 36 00 11 10 01 10 5 11 37 00 11 10 01 12 6 13 38 00 11 10 01 14 7 15 39 00 11 10 01 А В 18 9 19 41 00 11 10 01 16 8 17 40 00 11 10 01 20 10 21 42 00 11 10 01 22 11 23 43 00 11 10 01 24 12 25 44 00 11 10 01 26 13 27 45 00 11 10 01 28 14 29 46 00 11 10 01 30 15 31 47 00 11 10 01 А В 34 17 35 49 00 11 10 01 32 16 33 48 00 11 10 01 36 18 37 50 00 11 10 01 38 19 39 51 00 11 10 01 40 20 41 52 00 11 10 01 42 21 43 53 00 11 10 01 44 22 45 54 00 11 10 01 46 23 47 55 00 11 10 01 Входной бит = 0 Входной бит = 1 |