Основы теории принятая статистических решений 1051 38 страница

6. Здесь снова ни один из путей не имеет преимуществ. Декодер произвольно вы­бирает нулевой входной путь (или кодовое слово 11), и счетчик несовпадений возрастает до 2.

7. В момент и декодер принимает символы 10 и сравнивает их на четвертом уровне с кодовыми словами 00 и 11.

8. Здесь снова ни один из путей не имеет преимуществ, и декодер произвольно вы­бирает нулевой входной путь (или кодовое слово 00); счетчик несовпадений воз­растает до 3.

9. Поскольку счет несовпадений, равный 3, соответствует точке возврата, декодер “делает откат” и пробует альтернативный путь. Счетчик переустанавливается на

2 несовпадения.

10. Альтернативный путь на четвертом уровне соответствует пути входной битовой единицы (или кодовому слову 11). Декодер принимает этот путь, но после срав­нения его с принятыми символами 10 несовпадение остается равным 1, и счет­чик устанавливается равным 3.

11. Счет 3 является критерием точки возврата, поэтому декодер делает откат назад с этого пути, и счетчик снова устанавливается на 2. На данном уровне?₄ все аль­тернативные пути использованы, поэтому декодер возвращается на узел в мо­мент t_} и переустанавливает счетчик на 1.

12. В узле?₃ декодер сравнивает символы, принятые в момент времени?₃, а именно

1, с неиспользованным путем 00. В данном случае несовпадение равно 1, и счетчик устанавливается на 2.

13. В узле t₄ декодер следует за кодовым словом 10, которое совпадает с принятым в момент t₄ кодовым символом 10. Счетчик остается равным 2.

14. В узле?₅ ни один из путей не имеет преимуществ, и декодер, как и определяется правилами, следует верхней ветви. Счетчик устанавливается на 3 несовпадения.

15. При таком счете декодер делает откат, переустанавливает счетчик на 2 и пробует альтернативный путь в узле t_s. Поскольку другим кодовым словом является 00, снова получаем одно несовпадение с принятым в момент t_s кодовым символом

1, и счетчик устанавливается равным 3.

16. Декодер уходит с этого пути, и счетчик переустанавливается на 2. На этом уров­не ц все альтернативные пути использованы, поэтому декодер возвращается на узел в момент t₄ и переустанавливает счетчик на 1.

17. Декодер пробует альтернативный путь в узле /₄, метрика которого возрастает до 3, по­скольку в кодовом слове имеется несовпадение в двух позициях. В этот момент деко­дер должен сделать откат всех путей до момента?₂, поскольку все пути более высоких уровней уже использованы. Счетчик снова переустановлен на нуль.

18. В узле?₂ декодер следует кодовому слову 01. Поскольку имеется несовпадение в одной позиции с принятыми в момент?₂ кодовыми символами 00, то счетчик ус­танавливается на 1.

Далее декодер продолжает свои поиски таким же образом. Как видно из рис. 7.23, фи­нальный путь, счетчик которого не нарушает критерия точки возврата, дает правильно де­кодированную информационную последовательность 1 10 1 1. Последовательное декоди­рование можно понимать как тактику проб и ошибок для поиска правильного пути на ко­довом дереве. Поиск осуществляется последовательно; всегда рассматривается только один путь за раз. Если принимается неправильное решение, последующие пути будут ошибоч­ными. Декодер может со временем распознать ошибку, отслеживая метрики пути. Алго­ритм напоминает путешественника, отыскивающего путь на карте дорог. До тех пор, пока путешественник видит, что дорожные ориентиры соответствуют таковым на карте, он про­должает путь. Когда он замечает странные ориентиры (увеличение его своеобразной мет­рики), в конце концов приходит к выводу, что он находится на неправильном пути, и воз­вращается к точке, где он может узнать ориентиры (его метрика возвращается в приемле­мые рамки). Тогда он пробует альтернативный путь.

7.5.2. Сравнение декодирования по алгоритму Витерби с последовательным декодированием и их ограничения

Главный недостаток декодирования по алгоритму Витерби заключается в том, что в то время, как вероятность появления ошибки экспоненциально убывает с ростом длины кодового ограничения, число кодовых состояний, а значит сложность декодера, экспо­ненциально растет с увеличением длины кодового ограничения. С другой стороны, вычис­лительная сложность алгоритма Витерби является независимой от характеристики кана­ла (в отличие от жесткого и мягкого декодирования, которые требуют обычного увели­чения объемов вычислений). Последовательное декодирование асимптотически достигает той же вероятности появления ошибки, что и декодирование по принципу максимального правдоподобия, но без поиска всех возможных состояний. Фактически при последовательном декодировании число перебираемых состояний существенно не­зависимо от длины кодового ограничения, и это позволяет использовать очень большие (К = 41) длины кодового ограничения. Это является важным фактором при обеспечении таких низких вероятностей появления ошибок. Основным недостатком последователь­ного декодирования является то, что количество перебираемых метрик состояний явля­ется случайной величиной. Для последовательного декодирования ожидаемое число не­удачных гипотез и повторных переборов является функцией канального отношения сиг­нал/шум (signal to noise ratio — SNR). При низком SNR приходится перебирать больше гипотез, чем при высоком SNR. Из-за такой изменчивости вычислительной нагрузки, поступившие последовательности необходимо сохранять в буфере памяти. При низком SNR последовательности поступают в буфер до тех пор, пока декодер не сможет найти

7.6. Резюме

В течение последних десяти лет наиболее популярной схемой кодирования являлась сверточная, поскольку почти во всех приложениях сверточные коды лучше блочных при той же конструктивной сложности кодера и декодера. Для каналов спутниковой связи схемы прямого исправления ошибок позволяют легко понизить на 5-6 дБ тре­буемое значение SNR для заданной достоверности передачи. Из этой эффективности кодирования непосредственно вытекает снижение эффективной изотропной излучае­мой мощности спутника (effective isotropic radiated power — EIRP), что, соответствен­но, приводит к снижению веса и стоимости спутника.

В этой главе мы описали значительную структурную разницу между блочными и сверточными кодами — сверточные коды со степенью кодирования 1/л сохраняют в памяти предыдущие К - 1 бит, где К означает длину кодового ограничения. С такой памятью кодирование каждого входного бита данных зависит не только от значения этого бита, но и от предшествующих ему К - 1 бит. Задача описывалась в контексте алгоритма максимального правдоподобия. При его использовании изучаются все воз­можные последовательности кодовых слов, которые могли быть созданы кодером, и выбирается та, которая выглядит статистически наиболее вероятной. Решение опира­ется на метрику расстояния принятых кодовых символов. Анализ безошибочной рабо­ты сверточных кодов является более сложным, чем простое биномиальное разложе­ние, описывающее работу без ошибок многих блочных кодов. Здесь также введено понятие просвета и указана связь между просветом и границами надежной работы. Кроме того, в этой главе описаны основные идеи, касающиеся последовательного де­кодирования и декодирования с обратной связью, а также приведены некоторые сравнительные характеристики и таблицы различных схем кодирования.

Литература

1. Gallager R. G. Information Theory and Reliable Communication. John Wiley & Sons, Inc., New York, 1968.

2. Fano R. M. A Heuristic Discussion of Probabilistic Decoding. IRE Trans. Inf. Theory, vol. IT9. n. 2, 1963, pp. 64-74.

3. Odenwalder J. P. Optimal Decoding of Convolutional Codes. Ph. D. dissertation, University of Cali­fornia, Los Angeles, 1970.

4. Curry S. J. Selection of Convolutional Codes Having Large Free Distance. Ph. D. dissertation, Uni­versity of California, Los Angeles, 1971.

5. Larsen K. J. Short Conolutional Codes with Maximal Free Distance for Rates 1/2, 1/3, and 1/4. IEEE Trans. Inf. Theory, vol. IT19, n. 3, 1973, pp. 371—372.

6. Lin S. and Costello D. J. Jr. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Inc., Englewood Cliffs, N. J., 1983.

7. Forney G. D. Jr. Convolutional Codes: I. Algebraic Structure. IEEE Trans. Inf. Theory, vol. IT16, n. 6, November, 1970, pp. 720—738.

8. Viterbi A. Convolutional Codes and Their Performance in Communication Systems. IEEE Trans. Commun. Technol., vol. COM19, n. 5, October, 1971, pp. 751-772.

9. Forney G. D. Jr. and Bower E. K. A High Speed Sequential Decoder: Prototype Design and Test. IEEE Trans. Commun. Technol., vol. COM19, n. 5, October, 1971, pp. 821—835.

10. Jelinek F. Fast Sequential Decoding Algorithm Using a Stack. IBM J. Res. Dev., vol. 13, November, 1969, pp. 675-685.

11. Massey J. L. Threshold Decoding. The MIT Press, Cambridge, Mass., 1963.

Декодер с обратной связью реализует жесткую схему принятия решений относительно информационного бита в разряде j, исходя при этом из метрик, полученных из разря­дов j, j + 1, j + т, где т — заранее установленное положительное целое число. Дли­на упреждения (look-ahead length) L определяется как L = m+1, количество принятых кодовых символов, выраженных через соответствующее число входных битов, задейст­вованных для декодирования информационного бита. Решение о том, является ли информационный бит нулем или единицей, принимается в зависимости от того, на какой ветви путь минимального расстояния Хэмминга переходит в окне упреждения (look-ahead window) из разряда j в разряд j + га. Поясним это на конкретном примере. Рассмотрим декодер с обратной связью, предназначенный для сверточного кода со степенью кодирования 1/2, который показан на рис. 7.3. На рис. 7.25 приведена дре­вовидная диаграмма и работа декодера с обратной связью при L = 3. Иными словами, при декодировании бита из ветви j декодер содержит пути из ветвей j, j + 1 Hj + 2.

Начиная из первой ветви, декодер вычисляет 2¹ (восемь) совокупных метрик путей расстояния Хэмминга и решает, что бит для первой ветви является нулевым, если путь минимального расстояния содержится в верхней части дерева, и единичным, ес­ли путь минимального расстояния находится в нижней части дерева. Пусть принята последовательность Z = 1 10001000 1. Рассмотрим восемь путей от момента?, до момента ц в блоке, обозначенном на рис. 7.24 буквой А, и рассчитаем метрики, срав­нивая эти восемь путей для первых шести принятых кодовых символов (три ветви вглубь умножить на два символа для ветви). Выписав метрики Хэмминга общих путей (начиная с верхнего пути), видим, что они имеют следующие значения:

метрики верхней части 3, 3, 6, 4

метрики нижней части 2, 2, 1,3

Видим, что наименьшая метрика содержится в нижней части дерева. Следовательно, первый декодированный бит является единицей (и определяется сдвигом вниз на дере­ве). Следующий шаг будет состоять в расширении нижней части дерева (выживающий путь) на один разряд глубже, и здесь снова вычисляется восемь метрик, теперь уже для моментов t₂—t₄. Получив, таким образом, два декодированных символа, мы теперь мо­жем сдвинуться на два символа вправо и снова начать расчет метрик путей, но уже для шести кодовых символов. Эта процедура видна в блоке, обозначенном на рис. 7.25 бук­вой В. И снова, проследив метрики верхних и нижних путей, находим следующее:

метрики верхней части 2, 4, 3, 3

метрики нижней части 3, 1, 4, 4

Минимальная метрика для ожидаемой принятой последовательности находится в нижней части блока В. Следовательно, второй декодируемый бит также является единицей.

Таким образом, процедура продолжается до тех пор, пока не будет декодировано все сообщение целиком. Декодер называется декодером с обратной связью, поскольку найденное решение подается обратно в декодер, чтобы потом использовать его в оп­ределении подмножества кодовых путей, которые будут рассматриваться следующими. В канале BSC декодер с обратной связью может оказаться почти таким же эффектив­ным, как и декодер, работающий по алгоритму Витерби [17]. Кроме того, он может исправлять все наиболее вероятные модели ошибки, а именно — те, которые имеют весовой коэффициент (d_f- 1)/2 или менее, где d_f — просвет кода. Важным параметром

разработки сверточного декодера с обратной связью является L, длина упреждения. Увеличение L приводит к повышению эффективности кодирования, но при этом рас­тет сложность конструкции декодера.

fl t2 t₃ fs

oo

		00 a
	oo; a
		11 b
	00 a
	Ветвь			10 с
		111/3
СЛОВ
I	(	01 d
	00 a
			11 a
			10| с
				00 b
		11 b
			01 с
		i
		01 i d
		t	10 d
			t
a
			00! a
		11 i a
	i
	i	i	11 i b
		10 с
		i
				10! с
			oo: ь
			i
			01 Id
	11! ь
	i
			11;a
i		<У\\c
i i i		^jOOib 1 1 1
t i i i	01 d	i I i i i	^1_
i i		i	01 j с
i	i
i	10! d
а	l	i
		10jd
	Is
—_llj.—		01!	00! i

Принятая последовательность, шаг 1

Принятая последовательность, шаг 2 Рис. 7.25. Пример декодирования с обратной связью

вероятную гипотезу. Если средняя скорость передачи символов превышает среднюю скорость декодирования, буфер будет переполняться, вне зависимости от его емкости, и данные будут теряться. Обычно, пока идет переполнение, буфер убирает данные без ошибок, в то время как декодер пытается выполнить процедуру восстановления. Отме­тим, что порог переполнения буфера существенно зависит от SNR. Поэтому важным техническим требованием к последовательному декодеру является вероятность перепол­нения буфера.

На рис. 7.24 показаны типичные кривые, отображающие зависимость Р_в от EJN₀ для двух распространенных схем — декодирования по алгоритму Витерби и последовательного декодирования. Здесь сравниваются их характеристики при использовании когерентной модуляции BPSK в канале AWGN. Сравниваются кривые для декодирования по алгоритму Витерби (степень кодирования 1/2 и 1/3, К = 7, жесткое декодирование), декодирования по алгоритму Витерби (степень кодирования 1/2 и 1/3, К = 7, мягкое декодирование) и после­довательного декодирования (степень кодирования 1/2 и 1/3, К=41, жесткое декодирова­ние). Из рис. 7.24 можно видеть, что при последовательном декодировании можно достичь эффективности кодирования порядка 8 дБ при Р_в = 1СГ⁶. Поскольку в работе Шеннона (Shannon) [26] предсказывается потенциальная эффективность кодирования около 11 дБ, по сравнению с некодированной передачей с модуляцией BPSK, похоже, что, в основном, теоретически достижимые возможности уже получены.

12. Heller J. A. and Jacobs I. W. Viterbi Decoding for Satellite and Space Communication. IEEE Trans. Commun. Technol., vol. COM19, n. 5, October, 1971, pp. 835-848.

13. Viterbi A. J. Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm. IEEE Trans. Inf. Theory, vol. IT13, April, 1967, pp. 260—269.

14. Omura J. K. On the Viterbi Decoding Algorithm (correspondence). IEEE Trans. Inf. Theory, vol. IT15, January, 1969, pp. 177-179.

15. Mason S. J. and Zimmerman H. J. Electronic Circuits, Signals, and Systems. John Wiley & Sons, Inc. New York, 1960.

16. Clark G. C. and Cain J. B. Error-Correction Coding for Digital Communications. Plenum Press, New York, 1981.

17. Viterbi A. J. and Omura J. K. Principles of Digital Communication and Coding. McGraw-Hill Book Company, New York, 1979.

18. Massey J. L. and Sain М. K. Inverse of Linear Sequential Circuits. IEEE Trans. Comput., vol. C17, April, 1968, pp. 330-337.

19. Rosenberg W. J. Structural Properties of Convolutional Codes. Ph. D. dissertation, University of California, Los Angeles, 1971.

20. Bhargava V. K., Haccoun D., Matyas R. and Nuspl P. Digital Communications by Satellite. John Wiley & Sons, Inc., New York, 1981.

21. Jacobs I. M. Practical Applications of Coding. IEEE Trans. Inf. Theory, vol. IT20, May, 1974, pp. 305-310.

22. Linkabit Corporation. Coding Systems Study for High Data Rate Telemetry Links. NASA Ames Res. Center, Final Rep. CR-114278, Contract NAS-2-6-24, Moffett Field, Calif., 1970.

23. Odenwalder J. P. Error Control Coding Handbook. Linkabit Corporation, San Diego, Calif., July, 15, 1976.

24. Wozencraft J. M. Sequential Decoding for Reliable Commumication. IRE Natl. Conv. Rec., vol. 5, pt. 3, 1957, pp. 11-25.

25. Wozencraft J. M. and Reiffen B. Sequential Decoding. The MIT Press, Cambridge, Mass., 1961.

26. Shannon С. E. A Mathematical Theory of Communication. Bell Syst. Tech. J., vol. 27, 1948, pp. 379-423, 623-656.

Задачи

7.1. Нарисуйте диаграмму состояний, древовидную и решетчатую диаграммы для кода со сте­пенью кодирования 1/3 при К = 3, который имеет следующие генераторы:

g,(J0=X + X² g₂(J0 = l+X g₃(JQ=l+X + X²

7.2. Дан двоичный сверточный код со степенью кодирования 1/2 и К = Ъ с частично запол­ненной диаграммой состояний, изображенной на рис. 37.1. Найдите полную диаграмму состояний и опишите ее для кодера.

7.3. Нарисуйте диаграмму состояний, древовидную и решетчатую диаграммы для сверточного кодера, который описывается блочной диаграммой, показанной на рис. 37.2.

7.4. Допустим, что вы пытаетесь найти самый быстрый путь из Лондона в Вену поездом или на судне. Диаграмма на рис. 37.3 построена с учетом различных расписаний. Обозначения возле каждого пути являются временем путешествия. Используя алгоритм Витерби, най­дите наиболее быстрый маршрут из Лондона в Вену. Объясните, как работает этот алго­ритм, какие вычисления необходимо проделать и какие данные нужно сохранить в памяти для включения их в алгоритм.

7.5. Рассмотрим сверточный кодер, показанный на рис. 37.4.

а) Запишите векторы и полиномы связи для этого кодера.

б) Нарисуйте диаграмму состояний, древовидную и решетчатую диаграммы.

7.6. Какой будет импульсная характеристика в задаче 7.5? Используя эту характеристику, оп­ределите выходную последовательность, если на вход подается 10 1. Проверьте ответ с помощью полиномиальных генераторов.

7.7. Будет ли кодер, описанный в задаче 7.5, давать возможность для накопления катастрофи­ческой ошибки? Приведите пример в защиту своего ответа.

7.8. Найдите просвет для кодера из задачи 7.3, используя передаточную функцию.

7.9. Пусть кодовые слова в схеме кодирования имеют следующий вид.

I

fl=000000 *=101010 c=010101 ^=111111

Если по двоичному симметричному каналу принимается последовательность 1 1 1 0 1 0 и при этом осуществляется декодирование по принципу максимального правдоподобия, то каким будет декодированный символ?

7.10. Пусть на двоичном симметричном канале (binary symmetric channel — BSC) используется кодер со степенью кодирования 1/2 и К = 3, как показано на рис. 7.3. Допустим, что на­чальным состоянием кодера будет 00. На выходе канала BSC принимается последователь­ность Z = (1 100001011h остальное все “0”).

а) Найдите на решетчатой диаграмме максимально правдоподобный путь и определите первые 5 декодированных информационных битов. При наличии двух сливающихся путей выбирайте верхнюю ветвь.

б) Определите канальные биты в Z, которые подверглись искажению в ходе передачи.

7.11. Выясните, какие из следующих ниже кодов со степенью кодирования 1/2 будут катастро­фическими.

а) g.^X², g₂(X) = 1+Х + Х³

б) g,(X) = l+X^l,g₂(X) = l+X^s

в) _gl(X)=l+X+X², g^X^l+X + X’ + X⁴

г) g,(X) = 1+Х + Х³+ Х⁴, g₂(X) = 1 + X² + X⁴ _Д) g,(X) = 1 + Х⁴ + Х*+ Х⁷, g₂(X) = 1 + Х³ + Х⁴ е) g,(X) = l+X³ + X⁴, g₂(X)= 1+Х+Х² + Х⁴

7.12. а) Рассмотрим сигнал BPSK с когерентным детектированием, кодируемый с помощью кодера,

показанного на рис. 7.3. Найдите верхнюю границу вероятности появления битовой ошиб­ки, Р_в, если номинальное значение EJN₀ равно 6 дБ. Предполагается жесткое де­кодирование.

б) Сравните значение Р_в с некодированным случаем и определите выигрыш в отношении сигнал/шум.

7.13. С помощью последовательного декодирования изобразите путь вдоль древовидной диа­граммы, показанной на рис. 7.22, если принята последовательность 0 1 1 1 0 0 0 1 1 1. Критерием отката будет три несовпадения.

7.14. Повторите пример декодирования из задачи 7.13, воспользовавшись декодированием с об­ратной связью при длине упреждения 3. В случае появления связи выбирайте верхнюю часть дерева.

7.15. На рис. 37.5 показан сверточный кодер с длиной кодового ограничения, равной 2.

а) Нарисуйте диаграмму состояний, древовидную и решетчатую диаграммы.

б) Допустим, что от этого кодера поступило сообщение 110 0 10. Декодируйте это со­общение, воспользовавшись алгоритмом декодирования с обратной связью и считая длину упреждения равной 2.

7.16. С помощью данных об кодовом слове решетки кодера на рис. 7.7, декодируйте последова­тельность Z = (01 11 00 01 11, остальные все “0”), считая, что используется жесткая схема принятия решений и алгоритм декодирования Витерби.

7.17. Рассмотрим сверточный кодер со степенью кодирования 2/3, показанный на рис. 37.6. За раз в кодер подается к = 2 бит; п = 3 бит подается на выход кодера. Имеется кК = 4 разря­да регистра, и длина кодового ограничения равна К — 2 в единицах 2-битовых байтов. Со-

стояние кодера определяется как содержимое К - 1 крайних правых разрядов ^-кортежа. Нарисуйте диаграмму состояний, древовидную и решетчатую диаграммы.

Х-«

7.18. Найдите додетекторное значение спектральной плотности отношения сигнал/шум PJN₀, требуемое для получения скорости передачи декодированных данных в 1 Мбит/с, при ве­роятности появления ошибки 10~\ Предположите, что применяется двоичная некогерент­ная модуляция FSK. Также считайте, что осуществляется сверточное кодирование и

Р_в =2000/?*,

где р_с и Р_в — это вероятности появления ошибок внутри и вне декодера,.

7.19. Исходя из табл. 7.4, разработайте двоичный сверточный кодер со степенью кодирования 1/2 и К = 4.

а) Нарисуйте его блок-схему.

б) Нарисуйте решетку кодирования и обозначьте на ней состояния и кодовые слова.

в) Подберите ячейки, которые должны быть реализованы в алгоритме ACS.

7.20. Для следующей демодулированной последовательности выполните мягкое декодирование, используя код со степенью кодирования 1/2 и К = 3, который описывается схемой кодера, изображенной на рис. 7.3. Сигналы — это квантованные на 8 уровней целые числа от 0 до

7. Уровень 0 представляет собой идеальный двоичный 0, а уровень 7 — идеальную двоич­ную 1. Вход декодера: 6, 7, 5, 3, 1, 0, 1, 1, 2, 0, где крайнее левое число анляется самым первым. Декодируйте первые два бита данных, используя решетчатую диаграмму декоди­рования. Предположите, что кодер начинает из состояния 00 и процесс декодирования полностью синхронизирован.

Вопросы для самопроверки

7.1. Зачем нужна периодическая очистка регистра при сверточном кодировании (см. разде­лы 7.2.1 и 7.3.4)?

7.2. Дайте определение состоянию системы (см. раздел 7.2.2).

7.3. Что такое конечный автомат (см. раздел 7.2.2)?

7.4. Что такое мягкая схема принятия решений и насколько более сложным является мягкое де­кодирование по алгоритму Витерби в сравнении с жестким декодированием (см. разде­лы 7.3.2 и 7.4.8)?

7.5. Каково иное (описательное) название двоичного симметричного канала (binary symmetric channel — BSC) (см. раздел 7.3.2.1)?

7.6. Опишите расчеты процедуры сложения, сравнения и выбора (add-compare-select — ASC), ко­торые осуществляются в ходе декодирования по алгоритму Витерби (см. раздел 7.3.5).

7.7. На решетчатой диаграмме ошибка соответствует выжившему пути, который сначала расхо­дится, а затем снова сливается с правильным путем. Почему пути должны повторно сли­ваться (см. раздел 7.4.1)?

ГЛАВА 8

Канальное кодирование: часть 3

Символы сообщений

От других источников

Дата добавления: 2015-10-28