Эффективные модификации алгоритма Витерби в системах цифровой связи тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Натальин, Алексей Борисович

• Натальин, Алексей Борисович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Натальин, Алексей Борисович

Список основных сокращений и обозначений.

ВВЕДЕНИЕ.

1. Алгоритм Витерби и его применение в приемных устройствах цифровых систем связи.

1.1 Марковские цепи.

1.2 Обобщенный алгоритм Витерби.

1.3 Декодирование помехоустойчивых кодов.

1.3.1 Описание кодеров с помощью решетчатой диаграммы.

1.3.2 Помехоустойчивое декодирование по правилу максимума правдоподобия.

1.3.3 Протоколы коррекции ошибок.

1.4 Оценка данных, переданных по каналу связи с МСИ и АБГШ.

1.4.1 Максимально правдоподобная оценка данных в канале МСИ и АБГШ.

1.4.2 Уменьшение числа состояний в решетке за счет усечения сигнального созвездия.

1.4.3 Использование укорачивающего фильтра и алгоритма Витерби в канале связи с МСИ и АБГШ.

1.4.4 Методы синтеза укорачивающих фильтров для сигналов с модуляцией на многих несущих.

1.5 Совместная оценка импульсной характеристики канала и переданных данных.

1.5.1 Субоптимальная оценка канала с линейной вычислительной сложностью относительно длины последовательности.

1.5.2 Субоптимальная оценка канала с вычислительной сложностью, инвариантной к сигнальному созвездию.

1.6 Выводы.

2. Многовариантный алгоритм декодирования сверточных кодов и сигнально-кодовых конструкций.

2.1 Взаимодействие помехоустойчивого декодера с модулем коррекции ошибок.

2.2 Многовариантный декодер для стандартов передачи данных v32bis, v34 и протокола коррекции ошибок v42.

2.3 Энергетическая эффективность многовариантного декодера.

2.4 Выводы.

3. Укорачивающий фильтр и алгоритм Витерби с предсказанием шума.

3.1 Модель канала связи.

3.2 Результаты моделирования помехоустойчивости приемников, построенных на основе предложенных ранее алгоритмов.

3.3 Исследование степеней влияния источников шума.

3.4 Алгоритм Витерби с предсказанием шума.

3.5 Исследование приемника с укорачивающим фильтром и алгоритмом Витерби с предсказанием шума.

3.6 Сравнение вычислительных сложностей рассмотренных алгоритмов

3.7 Помехоустойчивость приемника с предсказанием шума в рэлеевском частотно-селективном канале связи.

3.8 Выводы.

4. Слепая оценка ИХ канала с пониженной вычислительной сложностью.

4.1 Описание алгоритма.

4.2 Результаты моделирования.

4.3 Выводы.

Введение диссертации (часть автореферата) на тему «Эффективные модификации алгоритма Витерби в системах цифровой связи»

Системы цифровой передачи информации играют огромную роль в современном мире и требования к скорости и надежности передаваемых данных постоянно растут. Аддитивный шум и межсимвольная интерференция (МСИ) являются основными факторами, которые приводят к появлению ошибок при передаче данных по каналу связи.

Причиной появления аддитивного шума в основном является широкополосный тепловой шум различных электронных компонентов. Для повышения энергетической эффективности практически во всех современных цифровых системах применяется помехоустойчивое кодирование.

Использование сверточных кодов и решетчатых сигнально-кодовых конструкций (СКК) в настоящее время является одним из наиболее популярных методов исправления ошибок. Причина этого кроется как в достаточно высокой корректирующей способности данных кодов, так и в существовании эффективных алгоритмов декодирования, которые основаны на отслеживании максимально правдоподобного решения по решетчатой диаграмме. Эти алгоритмы применимы и в случае использования демодулятора с мягким решением, что позволяет достичь максимально возможного энергетического выигрыша от кодирования [3].

Декодер Витерби является наиболее популярным среди алгоритмов декодирования, основанных на работе с решетчатой диаграммой, поскольку он позволяет получить максимально правдоподобную (МП) оценку переданного кодового слова [1-5]. Основным недостатком декодера Витерби является экспоненциальный рост вычислительной сложности при увеличении числа внутренних состояний кодера. Согласно основной теореме кодирования для сверточных кодов [1], путем увеличения числа внутренних состояний кодера можно достичь сколь угодно высокой надежности передаваемых данных в том случае, если скорость передачи не превосходит пропускной способности канала. Таким образом, использование сверточных кодов и решетчатых СКК с высокими корректирующими способностями вместе с декодером Витерби жестко ограничено доступными вычислительными ресурсами.

Алгоритм Витерби также может применяться для декодирования линейных блоковых кодов. Однако оптимальная треллис-структура линейного (п, к) кода имеет 2п~к внутренних состояний [4]. Это обстоятельство не позволяет реализовать на практике отслеживание решений по решетке для длинных блоковых кодов.

Кроме помехоустойчивого кодирования в некоторых системах связи для повышения надежности предоставляемых пользователю данных используется протокол коррекции ошибок [9], задача которого состоит в обнаружении ошибок на выходе помехоустойчивого декодера. Если таковые имеют место, ошибочный кадр либо вообще отбрасывается, либо, если в системе используется автоматический запрос повторения, приемная сторона просит передающую сторону повторить ошибочный кадр. Основными требованиями, накладываемыми на алгоритм обнаружения ошибок, являются малая (в сравнении с помехоустойчивым кодом) избыточность и малая (в сравнении с помехоустойчивым декодером) вычислительная сложность. В противном случае более разумным было бы потратить эти ресурсы не на обнаружение, а на исправление ошибок.

На данный момент алгоритмы декодирования помехоустойчивых кодов и протоколы коррекции ошибок на системном уровне рассматриваются независимо друг от друга. В данной работе предложен и исследован алгоритм взаимодействия помехоустойчивого декодера с модулем, реализующим протокол коррекции ошибок. Реализация данной идеи на практике может повысить помехоустойчивость приемников цифровых систем связи.

Передача сигналов в цифровых системах связи производится по аналоговым каналам связи, вносящим искажения в передаваемые данные. Это приводит к появлению МСИ на приемной стороне и может служить причиной появления ошибок на выходе приемника. Чтобы скомпенсировать возникающие искажения, необходимо производить выравнивание канала или оценку его импульсной характеристики (ИХ). Один из часто применяемых на практике методов заключается в том, что выравнивание и оценка ИХ канала основывается на известной приемнику обучающей последовательности, которая передается передатчиком в начале сеанса связи.

Выравнивание канала основано на использовании фильтра (эквалайзера), коэффициент передачи которого является обратным к коэффициенту передачи канала. В этом случае данные после прохождения канала и эквалайзера остаются неискаженными. Основным достоинством эквалайзеров является простота реализации. Однако в тех практических приложениях, где канал связи вследствие многолучевого распространения имеет спектральные нули, что имеет место, например, при передаче данных по радиоканалу в условиях городской застройки, эквалайзеры обладают в сравнении с МП оценкой переданных данных низкой помехоустойчивостью [5, 10].

В [9] было впервые показано, что МП оценка данных переданных при наличии МСИ, вызванной каналом с известной ИХ и аддитивным нормальным белым шумом может быть получена с помощью алгоритма Витерби. При этом число состояний в решетке экспоненциально зависит от длины ИХ канала, что не позволяет реализовать на практике МП приемник при большом времени рассеяния.

Один из способов снижения вычислительной сложности приемника состоит в использовании укорачивающих фильтров (УФ). В этом случае искажённый каналом и зашумленный сигнал пропускается через УФ, что эквивалентно прохождению сигнала через фильтр, ИХ которого является свёрткой ИХ канала и УФ. При этом ИХ УФ синтезирована таким образом, что большая часть энергии результирующей ИХ (целевое окно) сосредоточена в нескольких последовательных отсчетах, число которых меньше длины ИХ исходного канала. При обработке с помощью алгоритма Витерби предполагается, что сигнал был искажен только целевым окном результирующей ИХ, поэтому число состояний решетки и, соответственно, вычислительная сложность уменьшаются. Однако данный алгоритм не формирует МП оценку переданных данных, поскольку, во-первых, шум после прохождения через укорачивающий фильтр окрашивается, а во-вторых, передаваемые данные искажаются не только целевым окном результирующей ИХ.

В работах [16-20] были предложены различные варианты синтеза УФ. При этом для того, чтобы оценка данных была близка к МП оценке, в [16] требуется, чтобы основная энергия ИХ канала была сосредоточена в небольшом числе последовательных отсчетов. В [17] в полосе сигнала на любой частоте мощность сигнала должна быть много больше, чем спектральная плотность мощности (СПМ) шума, в [18] мощность сигнала, содержащаяся в первом пришедшим на приемник луче, должна значительно превосходить мощность шума. Укорачивающие фильтры, построенные на основе работ [19,20], окрашивают шум на входе алгоритма Витерби, что снижает помехоустойчивость приемника, построенного на основе фильтров синтезированных данными методами.

Результаты проведенного в данной работе численного моделирования показывают, что при рэлеевской модели канала с частотно-селективными искажениями непосредственное использование УФ и алгоритма Витерби приводит в сравнении с МП приемником к большим энергетическим потерям (около 8 дБ). При этом основной вклад в возникающие ошибки вносит коррелированность отсчетов шума на выходе УФ. Для снижения энергетических потерь в данной работе предложен алгоритм, который использует предсказание отсчетов коррелированного шума на выходе УФ.

В некоторых приложениях, таких, например, как многопользовательская сеть, передача обучающей последовательности для каждого вновь подключившегося пользователя привела бы к резкому падению средней скорости передачи. В этом случае применяются методы слепого выравнивания и оценки ИХ канала.

Методы слепого выравнивания в сравнении со слепыми методами оценок ИХ канала требуют гораздо меньшего объема вычислений при практической реализации, но имеют на 1-2 порядка большее время сходимости. Кроме того, многие методы слепого выравнивания не могут работать, если коэффициент передачи канала имеет нули в частотной области [5, 32].

В целях уменьшения времени сходимости и повышения надежности работы приемника используются МП и близкие к МП методы слепой оценки ИХ канала, реализация которых требует значительных вычислительных затрат. Существуют два основных подхода к формированию МП оценок ИХ канала: стохастический и детерминированный [5, 32]. В первом случае предполагается, что передаваемые данные представляют собой случайную последовательность с известными статистическими свойствами и оценке подлежит только ИХ канала, во втором случае совместно оцениваются и данные, и ИХ канала.

Метод совместной оценки канала и данных был впервые предложен в [33]. Вычислительная сложность представленного в [33] субоптимального алгоритма инвариантна к размеру используемого сигнального созвездия и экспоненциально растет с увеличением длины ИХ канала.

В данной работе предложен алгоритм совместной оценки ИХ канала и данных, основанный на использовании ОАВ. При этом у предложенного алгоритма вычислительная сложности имеет полиномиальную, а не экспоненциальную зависимость от длины ИХ канала, скорость сходимости такая же, как и у алгоритма представленного в [33]. Проведенные в данной работе исследования показали, что ограничением для применения предложенного алгоритма является интенсивность вызванных МСИ искажений.

Совокупность проведенных исследований позволяет сформулировать список положений, выносимых на защиту:

1. Алгоритм, позволяющий повысить помехоустойчивость приемных устройств за счет организации взаимодействия помехоустойчивого декодера Витерби с модулем коррекции ошибок;

2. Результаты исследований, позволяющие оценить достижимый выигрыш в помехоустойчивости и требуемые для этого вычислительные ресурсы;

3. Метод приема дискретных сигналов в частотно-селективных каналах связи, построенный на основе укорачивающего фильтра и алгоритма Витерби с предсказанием шума, обладающий пониженной вычислительной сложностью;

4. Результаты исследований, показывающих, что помехоустойчивость методов приема, построенных на основе укорачивающего фильтра и алгоритма Витерби, может быть заметно улучшена за счет использования линейного предсказания шума, при этом энергетический проигрыш оптимальному алгоритму приема будет незначительным;

5. Алгоритм формирования слепой оценки импульсной характеристики канала связи со слабой зависимостью вычислительной сложности от длины оцениваемой характеристики;

6. Результаты исследований времени формирования оценки для предложенного алгоритма при различных длинах и видах импульсных характеристик.

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

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Натальин, Алексей Борисович

4.3 Выводы

Представленные в данной главе результаты позволяют сделать следующие выводы:

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

2. Показано, что:

• представленный алгоритм позволяет сформировать оценку ИХ канала при умеренной интенсивности межсимвольной интерференции,

• максимально допустимая интенсивность МСИ определяется формой ИХ канала и не зависит от ее длины.

• время сходимости алгоритма лежит в диапазоне от 300 до 1000 символьных интервалов.

ЗАКЛЮЧЕНИЕ

Сформулируем основные результаты работы:

1 Предложен многовариантный алгоритм декодирования помехоустойчивых кодов и СКК, который основан на обратной связи между модулем коррекции ошибок и помехоустойчивым декодером. Показано, что:

• в системах связи с протоколами коррекции ошибок использование многовариантного декодера может повысить помехоустойчивость на 1-2 дБ, при этом выигрыш достигается за счет увеличения вычислительной сложности приемника;

• использование многовариантного алгоритма декодирования при разработке систем цифровой связи может повысить их энергетическую эффективность на 0,3-0,6 дБ. Выигрыш при этом достигается только за счет введения обратной связи помехоустойчивого декодера и модуля коррекции ошибок, без возрастания вычислительной сложности приемника.

2 Предложен метод приема дискретных сигналов, переданных по каналу связи с межсимвольной интерференцией и аддитивным былым гауссовым шумом, основанный на использовании укорачивающего фильтра и алгоритма Витерби с предсказанием шума. Показано, что:

• энергетический выигрыш предложенного метода составляет около 7 дБ в сравнении с существующими методами приема, основанными на использовании УФ и алгоритма Витерби, при этом выигрыш достигается за счет использования линейного предсказания шума;

• энергетический проигрыш предложенного приемника оптимальному алгоритму MLSE составляет около 2 дБ по уровню вероятности ошибки ЮЛ При этом вычислительная сложность предложенного алгоритма более чем в 150 раз меньше сложности алгоритма MLSE.

3 Предложен алгоритм слепой оценки импульсной характеристики канала при передаче КАМ-сигналов по частотно-селективному каналу связи.

Вычислительная сложность предложенного алгоритма имеет не экспоненциальную, а лишь полиномиальную зависимость от длины импульсной характеристики канала. Показано, что:

• представленный алгоритм позволяет сформировать оценку ИХ канала при умеренной интенсивности межсимвольной интерференции;

• максимально допустимая интенсивность МСИ определяется формой ИХ канала и не зависит от ее длины;

• время сходимости алгоритма лежит в диапазоне от 300 до 1000 символьных интервалов.

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

Список литературы диссертационного исследования кандидат технических наук Натальин, Алексей Борисович, 2007 год

1. Зигангиров К. Ш. Процедуры последовательного декодирования.— М.: Связь, 1974.

2. Витерби А. Д., ОмураДж. К. Принципы цифровой связи и кодирования.— М.: Радио и связь, 1982. — 536 с.

3. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. — М.: Радио и связь, 1987. — 392 с.

4. Branca Vucetic, Jinhong Yuan. Turbo codes: principles and applications: The Kluwer International Series in Engineering and Computer Science, 2000.

5. Прокис Дж. Цифровая связь. Пер. с англ./ Под ред. Д. Д. Кловского — М.: Радио и связь, 2000. — 800 е.: ил.

6. A Duplex Modem Operating at Data Signalling Rates of up to 14400 bit/s for Use on the General Switched Telephone Network and on Leased Point-to-Point 2-Wire Telephone-Type Circuits. ITU-T Recommendation V.32bis. ITU-T, Geneva, 1991.

7. A Modem Operating at Data Signalling Rates of up to 33 600 bit/s for Use on the General Switched Telephone Network and on Leased Point-to-Point 2-Wire Telephone-Type Circuits. ITU-T Recommendation V.34. ITU-T, Geneva, 1994.

8. Лагутенко О. И. Модемы. Справочник пользователя. СПб.: Лань, 1997.— 368 с.

9. G. David Forney, "Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference," IEEE Trans, on Information Theory, vol. IT-18, no. 3, May 1972, pp. 363-378.

10. Ю.Скляр Б. Цифровая связь. Теоретические основы и практическое применение, 2-е издание.: Пер. с англ. — М.: Издательский дом «Вильяме», 2003.

11. П.Тихонов В. И. Статистическая радиотехника, 2-е издание.— М.: Радио и связь, 624с., 1982.

12. Радиотехнические системы / Ю. П. Гришин, В. П. Ипатов, Ю. М. Казаринов и др.; Под ред. 10. М. Казаринова. — М.: Высш. шк., 1990. — 496 е.: ил.

13. УидроуБ., Стирз С., Адаптивная обработка сигналов. — М: Радио и связь, 1989.

14. М. Vedat Eyuboglu, Shahid U. H. Qureshi, "Reduced-State Sequence Estimation with Set Partitioning and Decision Feedback," IEEE Trans, on Communications, vol. 36, no. 1, January 1988, pp. 13-20.

15. G. Urgenboek, "Channel coding with multilevel/phase signals," IEEE Trans, on Information Theory, vol. IT-28, January 1982, pp. 55-67.

16. S. U. H. Qureshi and E. E. Newhal, "An Adaptive Receiver for Data Transmission over time-dispersive channels," IEEE Trans, on Information Theory, Vol. IT-19, July 1973, pp. 448-457.

17. C. Beare, "The Choice of the Desired Impulse Response in Combined Linear-Viterbi Algorithm Equalizers," IEEE Trans, on Communications, vol. 26, No. 8, August 1978, pp. 1301-1307.

18. W.Lee, F.Hill, "A Maximum Likelihood Sequence Estimator with Decision Feedback Equalization," IEEE Trans, on Communication, vol. 25, No. 9, September 1977, pp. 971-979.

19. D. Falconer and F. Magee, "Adaptive channel memory truncation for maximum likelihood sequence estimation," Bell Syst. Tech. J., vol. 52, No. 6, November 1977, pp. 1541-1562.

20. D. G. Messerschmitt, "Design of a finite impulse response for the Viterbi algorithm and decision feedback equalizer," IEEE Int. Conf. on Communications, Minneapolis, June 1974.

21. J. Chow and J. M. Cioffi, "A cost-effective maximum likelihood receiver for mul-ticarrier systems," Int. Conf. on Communications, Chicago, June 1992, pp. 948952.

22. N. Al-Dhasir and J. M. Cioffi, "Efficiently Computed Reduced-Parameter Input-Aided MMSE Equalizers for ML detection: A Unified Approach," IEEE Trans, on Information Theory, Vol. 42, No. 3, May 1996, pp. 903-915.

23. P. J. W. Melsa, R. C. Younce, and С. E. Rohrs, "Impulse response shortening for discrete multitone transceivers," IEEE Trans, on Communications, vol. 44, December 1996, pp. 1662-1672.

24. G. Arslan, B. L. Evans, and S. Kiaei, "Equalization for Discrete Multitone Receivers To Maximize Bit Rate," IEEE Trans, on Signal Processing, vol. 49, no. 12, Dec. 2001, pp. 3123-3135.

25. ITU-T Recommendation, G.992.2, Splitterless asymmetric digital subscriber line (ADSL) transceivers, June 1999.

26. J. Louveaux, L. Vandendorpe, and T. Sartenaer, "Cyclic prefixed single carrier and multicarrier transmission: Bit rate comparison," IEEE Commun. Lett., vol. 7, no. 4, Apr. 2003, pp. 180-182.

27. Z. Wang, X. Ma and G. B. Giannakis, "OFDM or Single-Carrier Block Transmissions?," IEEE Trans, on Communications, vol. 52, no. 3, March 2004, pp. 380— 394.

28. Y. Saito, "A Method of Self-Recovering Equalization for Multilevel Amplitude Modulation," IEEE Trans, on Communications, Vol. COM-29, June 1975, pp. 679-683.

29. G. Picchi and G. Prati, "Blind Equalization and Carrier Recovery Using a Stop-and-Go Decision Directed Algorithm," IEEE Trans, on Communications, Vol. COM-35, September 1987, pp. 877-887.

30. J. K. Tugnait, L. Tong, and Z. Ding, "Single-User Channel Estimation and Equalization," IEEE Signal Processing Magazine, vol. 17, No. 3, May 2000, pp. 16-29.

31. N. Seshadri, "Joint Data and Channel Estimation Using Blind Trellis Search Techniques", IEEE Trans, on Communications, vol. COM-42, March 1994, pp.1000-1011.

32. Chong-Yung Chi, Ching-Yung Chen, Chi-Horng Chen, and Chin-Chun Feng, "Batch Processing Algorithms for Blind Equalization Using Higher-Order Statistics", IEEE Signal Processing Magazine, vol. 20, No. 1, January 2003, pp. 25-50.

33. MATLAB Statistics Toolbox User's Guide. — The Math Works, Inc., 2007. 36.S. Haykin. Adaptive filter theory. — Prentice-Hall, NJ, 1986.

34. Френкс Л. Теория сигналов. / Пер. с англ., под ред. Д. Е. Вакмана. — М.: Сов. радио, 1974.