Конспект лекции по ТЭС
.pdf
a2 , a1, a0 b2 , b1, b0
a2 , a1, a0 b0
a2 , a1, a0 b1
a2 , a1, a0 |
b2 |
c4 , c3 , c2 , c1, c0 |
|
Каждый коэффициент результата находится с помощью дискретной свёртки последовательностей коэффициентов входного многочлена и множителя (правило 3):
n |
|
ck bi ak i , k 0,1,... , |
(74) |
i 0
где ai 0 при i 0 .
Схема реализации умножения многочленов на основе регистра сдвига
В начальном состоянии ячейки регистра сдвига содержат нули. Для вычисления всего результата в регистр дополнительно в конце вводят нули, пока последний символ входного многочлена не пройдёт через регистр.
+
|
|
|
b0 |
|
b1 |
|
|
b2 |
|
|
bn |
|
|
|||
0,...,0,0 , a ..., a , a , a |
|
|
|
|
|
|
|
|
|
… |
|
|
|
..., c |
, c , c |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
m 2 1 0 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
1 0 |
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 4. Схема реализации умножения многочленов.
Деление многочленов
где
a(x) a0 a1x a2 x2 ... am xm b(x) b0 b1x b2 x2 ... bn xn
c(x) c0 c1x c2 x2 ... cm n xm n
c(x) |
a(x) |
, |
(75) |
|
b(x) |
||||
|
|
|
– делимое,
– делитель,
– частное.
Степень частного |
|
|
|
|
|
|
|
deg(a(x)) deg(b(x)), при |
deg(a(x)) deg(b(x)), |
||||||||||||||||||||
deg(c(x)) 0, deg(a(x)) deg(b(x)), c |
0. |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
deg(a(x)) deg(b(x)) , |
|
|
|
|
0 |
|
||||||||||||||||
Если |
то результатом деления является многочлен степени 0 с |
||||||||||||||||||||||||||||
коэффициентом c0 |
0 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
Деление многочленов реализуется с помощью алгоритма деления столбиком: |
|||||||||||||||||||||||||||||
a0 , |
a1 , |
a2 |
|
|
|
|
|
|
|
|
|
|
|
b0 , b1 |
|
|
|
|
|
|
|
|
|||||||
a0 , |
a0 |
b1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
a |
|
1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
c0 , a1 |
|
|
0 |
b1 |
|
c1 |
|
||||||
b0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b |
b |
b |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
0 |
0 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
a |
a0 |
b , |
a |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
1 |
|
|
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
b0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
a |
|
a |
0 |
|
|
|
b |
|
|
|
|
|
|
|
|
|
|
|
||||||||
a1 |
|
|
|
0 |
b1 , a1 |
|
|
|
b1 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
b |
b |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
b |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
0 |
|
0 |
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
a0 |
|
|
b1 |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
a2 a1 |
|
|
b1 |
|
|
– остаток |
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
b |
|
b |
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|||||
140
Схемы реализации деления многочленов на основе регистра сдвига Математическая формула деления. Вычисление очередного коэффициента частного
можно выразить через значения ранее вычисленных коэффициентов (рекурсивная формула) следующим образом:
c(x)
c(x)
где c0 a0 , b0
a(x) |
a(x) |
|
1/ b0 |
|
|
|
c(x) c(x)x b1 (x) |
1 |
a(x) |
1 |
|
||||||||||||||
b(x) |
|
|
|
|
|
|
x |
|
b0 |
b0 |
|||||||||||||||
|
|
1 b1 |
(x) |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
b0 |
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
1 |
a(x) c(x)x b1 (x) ck |
|
1 |
|
n 1 |
|
|
|
|
|
|
||||||||||||||
|
|
|
ak |
bi 1 ck 1 i |
|
|
|||||||||||||||||||
b |
b |
|
|||||||||||||||||||||||
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
i 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
n |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
bi |
|
, |
|
|
|
(76) |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
ck |
|
ak |
ck i |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
b |
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
i 1 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
a0 |
1 |
и т.д. |
|
|
|
|
|
|
|
|
|
|
|
||||||||
c1 |
a1 |
|
|
b1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
b |
b |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Схема 1. Вычисляет только частное. В начальном состоянии все ячейки содержат нули.
+
b1 |
b2 |
|
b3 |
|
bn |
|
|
|
|
|
|
..., a2 , a1 , a0 |
+ |
|
b0 |
|
|
|
|
… |
|
..., c2 , c1, c0 |
||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 5. Схема реализации деления многочленов.
Схема 2. Вычисляет и частное и остаток. В начальном состоянии все ячейки заполнены первыми n 1 коэффициентами входного многочлена.
..., c2 , c1, c0
|
|
|
bn |
|
|
|
|
|
|
b2 |
|
|
|
|
b1 |
|
|
|
1 |
|
||
|
|
|
|
|
|
|
|
|
|
|
b0 |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
am 1 ,..., an 1 |
, an |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
+ |
|
an 1 |
… |
a2 |
|
|
+ |
|
a1 |
|
|
+ |
|
|
a0 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 6. Схема реализации деления многочленов на основе регистра сдвига с обратной связью.
После вычисления последнего коэффициента многочлена частного в регистре сдвига будут содержаться коэффициенты многочлена остатка:
r(x) a(x) mod b(x) r |
r x ... r |
xn 1 . |
(77) |
|
0 |
1 |
n 1 |
|
|
Степень многочлена остатка deg r(x) deg b(x) .
141
Пример кодирования и декодирования
Для реализации кодирования и декодирования комбинаций циклического кода достаточно выбрать порождающий многочлен кода g(x) . Существуют таблицы
порождающих многочленов кодов для разных длин кода и числом информационных символов (Р.Блейхут. Теория и практика кодов, контролирующих ошибки. – М.:«Мир», 1986, Дж.Кларк, Дж.Кейн. Кодирование с исправлением ошибок в системах цифровой связи. – М.:«Радио и связь», 1987).
Например, для кода Хэмминга (7,4) g(x) x3 x 1, (15,11) g(x) x4 x 1.
Пусть b(x) x3 x2 (1100) – информационный многочлен. Несистематическое кодирование:
c(x) b(x)g(x) (x3 x2 ) (x3 x 1) x6 x5 x4 x2 (1110100) .
Систематическое кодирование:
c(x) b(x)xn k r(x) (x3 x2 ) x3 x x6 x5 x (1100010) , где r(x) b(x)xn k mod g(x) x6 x5 mod x3 x 1 x (010) .
Передача по дискретному каналу кодовой комбинации систематического кода: e(x) x4 (0010000) ,
y(x) c(x) e(x) x6 x5 x4 x (1100010) (0010000) (1110010) .
Синдром:
s(x) y(x) mod g(x) (x6 x5 x4 x) mod(x3 x 1) x2 x (110) .
По таблице синдромов этот синдром соответствует ошибке в 4 символе, т.е. eˆ(x) x4 (0010000) .
Тогда cˆ(x) y(x) eˆ(x) x6 x5 x (1100010) .
142
Свёрточные коды
Свёрточные коды относят к непрерывным линейным кодам, для которых, в отличие от блочных кодов, кодовые комбинации на выходе кодера нельзя отделить друг от друга.
Такое название они получили из-за способа кодирования, в котором выходная последовательность кодовых символов получается в результате дискретной свёртки последовательности входных символов и порождающих многочленов кода.
Свёрточный код со скоростью кода Rc k / n обозначается (n, k, d f ) , где d f – его свободное расстояние.
Схема свёрточного кодера
Свёрточныё кодер со скоростью Rc k / n имеет k входов и n выходов.
Дискретная свёртка реализуется с помощью регистра сдвига с отводами, поэтому в состав любого кодера входит не менее k регистров сдвига.
При кодировании на каждом такте на вход кодера подаётся k информационных символов, каждый из которых записывается в свой регистр сдвига. В соответствии с заданными отводами и с учётом предыдущих v информационных символов, вновь поступившие символы кодируются в n кодовых символов, которые кодер по очереди выдаёт на своём выходе.
Параметр v называется кодовым ограничением. Для кода со скоростью Rc |
1/ n он |
||||||
равен длине регистра сдвига кодера минус 1. |
|
||||||
На следующем рисунке представлена схема свёрточного кодера (2,1,5) со скоростью |
|||||||
Rc 1/ 2 и v 2 . |
|
|
|
|
|
|
|
|
|
|
+ |
|
|
|
|
..., b , b , b |
|
|
|
..., c21 , c20 , c11 , c10 , c01 , c00 |
|
||
|
|
|
|
||||
2 |
1 |
0 |
|
|
|
|
|
|
|
|
+ |
|
|
|
|
Рисунок. 7. Схема свёрточного кодера (2,1,5) со скоростью R 1/ 2 . |
|
||||||
Порождающие многочлены этого свёрточного кода равны |
|
||||||
g0 (x) 1 x x2 |
(задаёт верхние отводы регистра сдвига), |
(78) |
|||||
g (x) 1 x2 |
(задаёт нижние отводы регистра сдвига). |
(79) |
|||||
1 |
|
|
|
|
|
|
|
До начала кодирования содержимое ячеек регистра сдвига равно нулю.
При кодировании содержимое регистра сдвига сдвигается вправо, причём содержимое последней (самой крайней справа) ячейки отбрасывается, а в первую ячейку регистра сдвига записывается очередной символ. Далее, соответствующие символы суммируются в верхнем и нижнем сумматорах, и результирующие кодовые символы по очереди выдаются на выходе кодера. Суммирование выполняется по модулю 2.
Алгоритм Витерби декодирования свёрточных кодов
Для декодирования свёрточных кодов с небольшим кодовым ограничением обычно используется алгоритм декодирования Витерби (1967), эффективно реализующий правило максимального правдоподобия декодирования последовательности кодовых символов.
В этом алгоритме используется решётка декодирования, с помощью которой удаётся значительно сократить общее число всевозможных перебираемых последовательностей
143
кодовых символов. Высота решётки равна 2v и не зависит от длины декодируемой последовательности. Сложность реализации алгоритма пропорциональны этой величине.
На рисунке 8 изображено одно звено решётки декодирования свёрточного кода (2,1,5), кодер которого представлен на предыдущем рисунке.
Узлы решётки определяют состояние кодера. На ветвях отмечены кодовые символы, выдаваемые кодером при переходе из предыдущего состояния в следующее состояние.
0 |
00 |
|
11 |
||
|
||
1 |
11 |
|
00 |
||
|
10
2 |
01 |
01
3
10
Рисунок. 8. Одно звено решётки декодирования свёрточного кода со скоростью Rc 1/ 2 и v 2 .
На вход декодера поступают последовательности кодовых символов zk . Согласно
алгоритму Витерби, в процессе декодирования на решётке строятся пути всевозможных последовательностей кодовых символов, которые наиболее близки по Хеммингу к последовательности символов zk на входе декодера.
Расстояние по Хеммингу между последовательностями символов равно числу символов, в которых они отличаются. Это расстояние называют метрикой пути.
В каждом узле решётки соединяются два пути, но дальше продолжится только тот путь, чья метрика будет минимальной. Этот путь называют выжившим путём.
После поступления очередных символов декодер сначала вычисляет приращения метрик путей, которые затем прибавляются к метрикам путей, вычисленных на предыдущем шаге. Приращение метрики пути – это расстояние по Хеммингу между символами на входе декодера и символами соответствующей ветви.
По окончании поступления символов на вход декодера, в качестве решения выдаётся последовательность информационных символов, чей путь по решётке будет иметь наименьшую метрику среди всех выживших путей.
Теоретически, задержка между началом поступления символов на вход декодера и выдачей решения на его выходе равна бесконечности. Но при практической реализации решения начинают выдавать уже после поступления некоторого конечного числа D символов. После приёма D символов, в качестве решения выдаётся первый символ пути, метрика которого наименьшая в данный момент. Далее вычисляют метрики для очередного символа и в качестве решения выдаётся второй символ пути, текущая метрика которого минимальна. Этот процесс продолжается до тех пор, пока не будут приняты все символы.
Исследования показали, что для декодирования достаточно выбрать D (3...5)v . При выборе больших значений качество работы декодера увеличивается незначительно.
Рассмотрим процесс декодирования рассмотренного ранее кода при передаче последовательности из одних нулей, когда на вход декодера поступает последовательность {zk } 01,10, 00, 00, 00, 00,... (в канале произошло две ошибки).
На следующих рисунках изображены последовательные шаги построения решётки. В кружках отмечаются текущие метрики выживших путей, а отброшенные пути обозначены штриховой линией.
144
