Использование жесткого и мягкого алгоритма витерби в программе для декодирования текстового сообщения
Разработка программной модели и декодирования текстового сообщения, полученного по каналу с аддитивным гауссовским шумом, методом использования многопозиционной фазовой манипуляции, число позиций может быть задано пользователем. Методы защиты от ошибок.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | статья |
Язык | русский |
Дата добавления | 30.04.2018 |
Размер файла | 897,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Использование жесткого и мягкого алгоритма витерби в программе для декодирования текстового сообщения
Чернецова Е.А.
Шишкин А.Д
Кандидат технических наук, доцент,
Российский Государственный Гидрометеорологический Университет
Аннотация
Представлена программная модель декодирования текстового сообщения, полученного по каналу с аддитивным гауссовским шумом. Для передачи сигнала используется многопозиционная фазовая манипуляция, число позиций может быть задано пользователем. Для защиты от ошибок используется сверточный код, параметры которого могут быть заданы пользователем. При декодировании используется мягкий и жесткий алгоритм Витерби. Наглядность представления выходных данных - исходного текстового сообщения и декодированных сообщений - позволяет использовать данную программу в учебном процессе при изучении темы сверточного кодирования.
Ключевые слова: программная модель, кодер, декодер, алгоритм, многофазная манипуляция.
Abstract
A software model for decoding a text message received via a channel with additive Gaussian noise is presented. A multi-position phase shift keying is used for signal transmission; the number of positions can be set by the user. To protect against errors, a convolutional code is used, the parameters of which can be set by the user. Soft and hard Viterbi algorithm is used at decoding. The obviousness of the output data, the source text message, and decoded messages allows using this program in the learning process when studying the subject of convolutional coding.
Keywords: software model, encoder, decoder, algorithm, multiphase keying.
При изучении принципов построения телекоммуникационных систем в рамках дисциплины «Системы и сети передачи информации» [1] , студенты часто испытывают трудности с пониманием алгоритма работы мягкого и жесткого декодирования Витерби. Поэтому была поставлена цель создать программную модель, которая могла бы наглядно продемонстрировать обучающимся разницу в приеме информации, передаваемой по каналу с аддитивным белым гауссовским шумом в незакодированном и закодированном виде, и продемонстрировать результат декодирования текстового сообщения с использованием жесткого и мягкого алгоритма Витерби. Широкое распространение алгоритма Витерби заключается в том, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов [2].
В программной реализации используется многофазная манипуляция. Данный вид модуляции был выбран потому, что он может быть использован в каналах связи, имеющих достаточно ограниченный частотны ресурс, но к которым предъявляются высокие требования по качеству передачи информации [3]. Согласно [4], к основным показателям, характеризующим тот или иной модуляционный формат, следует отнести помехоустойчивость и спектральную эффективность, под которой понимают полосу частот, необходимую для передачи сигналов с требуемой скоростью и достоверностью. программный канал декодирование пользователь
В общем случае, данные показатели тесно взаимосвязаны между собой. Это приводит к тому, что улучшение одного из них невозможно без снижения качества другого. Между тем, переход на цифровые системы передачи информации во многом предопределил типы используемых модуляционных форматов, к которым, в первую очередь, следует отнести различные виды манипуляций, как наиболее полно соответствующих дискретной природе передаваемой битовой информации.
Однако, возможности широко известных форматов манипуляции фактически исчерпаны, а их дальнейшая модернизация не позволяет получить существенного выигрыша. В связи с этим, в последнее время наметилась тенденция на переход к формированию сигналов в базисах, отличных от гармонических [5], [6]. В частности, вейвлет-базисы, базисы сплайн-характеров и др. Однако такой подход предполагает полную замену приемо-передающего оборудования, что сложно осуществить в существующих реалиях. Между тем, по мнению зарубежных специалистов [7], [8], традиционные виды модуляции еще до конца не исчерпали свои возможности. Повышению скорости передачи информации в канале способствует увеличение позиционности модуляционного формата, однако при этом возрастает битовая ошибка. В настоящее время компромиссным решением для систем передачи информации по радиоканалу является использование модуляционных форматов на основе ФМн-2 и ФМн-4 [7]. В разработанной программе число позиций модуляции можно задавать.
Модели систем, представленные в пакете МатлабSimulink для реализации жесткого и мягкого декодирования по алгоритму Витерби [9] разработаны для исходных данных, представляющих собой поток битов.
Модель декодера Витерби для детектирования двоичного фазоманипулированного сигнала, представленная в [10], также разработана для исходных данных, представляющих собой поток битов, и реализует только алгоритм жесткого декодирования Витерби .
По сравнению с рассмотренными моделями систем, реализующими жесткое и мягкое декодирование по алгоритму Витерби [9], [10], разработанная программа в пакете Матлаб предназначена для исходных данных, представленных в виде текстового сообщения, и позволяет студентам ознакомиться с программным кодом, реализующим все преобразования сообщения от текстового вида до сигнала в фазовой или квадратурной фазовой манипуляции. Студенты также получают представление о формировании алгоритма кода Грея, когда двоичные символы отличаются только одной битовой позицией. В этом случае при появлении ошибки в М-арном символе высока вероятность того, что ошибочным является только один из k прибывших битов [11]. Несмотря на то, что в версиях Матлаб, появившихся после 2006 года, предусмотрена реализация алгоритма кода Грея в виде одной команды, предлагаемая программа позволяет студентам не только посмотреть график получившегося сигнального созвездия, но и реализовать алгоритм кода Грея «пошагово», тем самым закрепив их знания об алгоритме его формирования.
Для реализации декодирования Витерби в программной модели используетсятот факт, что данный алгоритм используется в двоичном входном канале с жестким или мягким 3-х битовым квантованным выходом. Длина кодового ограничения варьируется от 3 до 9, причем степень кодирования кода редко оказывается меньше 1/3, и память путей составляет несколько длин кодового ограничения. [12]. В алгоритме декодирования Витерби все пути по решетке кода пошагово сравниваются с принятой из канала связи кодовой последовательностью и отбрасываются те из них, которые точно будут находиться на большем расстоянии, чем другие. Таким образом, главным недостатком данного алгоритма становится необходимость анализа всех путей, выходящих из рассматриваемого узла кодовой решетки. Этот недостаток легко преодолевается благодаря большим вычислительным возможностям современных компьютеров. А благодаря тому, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов , он находит широкое применение в современных цифровых системах связи. Алгоритм декодирования Витерби также хорошо использовать в тех случаях, когда шум в канале связи стационарен и легко моделируется.
В жесткой схеме декодирования по алгоритму Витерби используется расстояние Хэмминга, определяемое как количество элементов, которыми различаются два кодовых слова.
Основное различие между мягким и жестким декодированием по алгоритму Витерби состоит в том, что в мягкой схеме не используется метрика расстояния Хэмминга, поскольку она имеет ограниченное разрешение. Метрикой расстояний, которая имеет нужное разрешение, в данном случае выступает евклидово кодовое расстояние, поэтому, чтобы облегчить ее применение в программной модели соответствующим образом преобразуются двоичные числа из единиц и нулей в восьмеричные числа от 0 до 7. Выигрыш в значении битового отношения сигнал/шум при использовании «мягкого» решения составляет EbNo? 2 дБ ( рис.1) [13].
Алгоритм программы состоит из следующей последовательности действий:
1. Ввод текстовой строки сообщения.
2. Преобразование текста в ASCII -код.
3. Преобразование символов ASCII -кода в бинарные символы.
4. Формирование из бинарных символов последовательности бит для подачи на вход кодера.
5. Кодирование бинарной последовательности кодом Грея
6. Кодирование бинарной последовательности сверточным кодом для защиты от ошибок
7. Применение фазовой манипуляции к закодированной и незакодированной последовательности битов. Возможность выбора параметров манипуляции.
8. Моделирование прохождения закодированной и незакодированной последовательности битов через канал с гауссовым шумом. Возможность выбора отношения сигнал/шум в канале связи.
9. Демодуляция закодированной и некодированной последовательности бит
10. Декодирование закодированной последовательности бит с использованием жесткого и мягкого алгоритма Витерби.
11. Расчет квадрата евклидова расстояния между исходным текстовым сообщением и принятыми сообщениями: не подвергавшимся кодированию; декодированному по жесткому алгоритму Витерби и декодированному по мягкому алгоритму Витерби. Определение ассимптотической эффективности кодирования.
Результат работы программной модели при значении битового отношения сигнал/шум EbNo=4,5 дБ представлен на рисунке 2. Как можно видеть, сообщение , декодированное с помощью «мягкого» алгоритма полностью совпадает с исходным, тогда как в принятом некодированном сообщении и в сообщении, декодированном с помощью «жесткой» схемы, есть ошибки.
Риc. 1 - Графики зависимости вероятности битовой ошибки от битового отношения сигнал/шум
Асимптотическая эффективность кодирования в программе определяется по формуле:
G(дБ) = (1)
где df и dэт - евклидов просвет кодированной системы и некодированной эталонной системы.
Рис. 2 - Результат работы программной модели декодирования текстового сообщения при значении битового отношения сигнал/шум EbNo=4,5 дБ с использованием жесткого и мягкого алгоритма Витерби
В программе метрика dэт представляет собой количество битовых ошибок между принятым некодированным и исходным сообщением, а метрика df представляет собой количество битовых ошибок между принятым кодированным и исходным сообщением, которые вычисляются с помощью команды Матлабbiterr.
Студенты должны написать сами код для реализации данной модели, используя знания, умения и навыки, полученные ими при прохождения практики «Программирование и цифровая обработка сигналов в пакете Матлаб». Разработанная программа оставляет студентам простор для творчества, поскольку к данной программной модели студентам предлагается самостоятельно написать программу графического интерфейса пользователя.
Таким образом, рассмотренная программа позволяет студентам применить на практике знания, полученные при изучении темы помехоустойчивого кодирования, изучаемой в рамках дисциплины «Системы и сети передачи информации».
Список литературы / References
1. Белов Е.Б. Сборник примерных программ учебных дисциплин по направлению подготовки (специальности) 090302 «Информационная безопасность телекоммуникационных систем» (квалификация (степень) «специалист»)/ Е.Б. Белов - М.: МГУПИ, 2011. - 220 с.
2. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник / под.ред. Ю. Б. Зубарева. - М.: Горячая линия -Телеком, 2004. - 126 c.
3. Дворников С.В. Спектрально эффективные сигналы с непрерывной фазой/ С.В.Дворников, С.С.Дворников, С.С. Манаенко и др. // Вестник воронежского государственного технического университета. - 2016. - Т. 12. - № 2. - С. 87-93
4. Федосеев В.Е. Методика и результаты анализа потенциальной помехоустойчивости приема цифрового сигнала на фоне манипулированной структурной помехи/ В.Е.Федосеев, М.С. Иванов // Вестник Воронежского государственного технического университета. - 2010. - Т. 6. - № 11. - С. 108-111
5. Дворников С.В. Помехоустойчивость фазоманипулированных сигналов на основе вейвлетов Гаусса/ С.В.Дворников, С.С.Манаенко// Вестник Воронежского государственного технического университета. -2015. - Т. 11. - № 3. - С. 123-125.
6. Дворников С.В. Синтез манипулированных сигналов на основе вейвлет-функций/ С.В.Дворников, С.С.Дворников, А.М. Спирин // Информационные технологии. - 2013. - № 12. - С. 52-55
7. Hong and K. C. Ho. Classification of BPSK and QPSK signals with unknown signal level using the Bayes technique. in Proc. IEEE ISCAS, 2003, pp. IV.1-IV.4.
8. Panagiotou, A. Anastasoupoulos, and A. Poly-doros. Likelihood ratio tests for modulation classification. in Proc. IEEE MILCOM, 2000, pp. 670 - 674.
9. ViterbiDecoder [Электронный ресурс] - URL: www.mathworks.com/help/comm/ref/viterbidecoder.html (дата обращения: 23.02.2018)
10. Варкасов Р.С. Разработка наглядной математической модели декодера Витерби для детектирования двоичного фазоманипулированного сигнала/ Р.С.Варкасов, И.М. Лернер //Научный Альманах. -2015. - № 8 (10). - С.749-751
11. Чернецова Е.А. «Системы и сети передачи информации» . Часть 1. Телекоммуникационные сети/ Е.А.Чернецова - СПб.: Изд-во РГГМУ. -2013. - 156 с.
12. Скляр Б. Цифровая связь. Теоретические основы и практическое применение/ Б.Скляр. - М.: Вильямс. - 2016. - 1104 с.
13. LLR vs. HardDecisionDemodulation [Электронный ресурс] -URL: www.mathworks.com/help/comm/examples/llr-vs-hard-decision-demodulation.html (дата обращения: 23.02.2018)
Размещено на Allbest.ru
Подобные документы
Принципы защиты от ошибок информации при ее передаче по каналам связи. Блоковые коды и методы их декодирования. Построение линейных блочных аддитивных алгебраических кодов и принципы их декодирования синдромным методом. Основные возможности SciLab.
курсовая работа [394,4 K], добавлен 17.05.2012Разработка программной базы для исследований в области распознавания речи и поиска ключевых слов в ней. Расчет mel-фильтров. Скрытые марковские модели. Применение в алгоритме сверточного декодирования Витерби. Методы визуализации и обработки аудиоданных.
курсовая работа [1,1 M], добавлен 01.06.2015Разработка программы кодирования текстового файла при помощи блочного алгоритма шифрования ТЕА типа "Сеть Фейштеля", который основан на битовых операциях с 64-битным блоком и имеет 128-битный ключ шифрования. Результаты кодирования и декодирования.
лабораторная работа [299,9 K], добавлен 18.07.2013Сущность метода перестановочного декодирования. Особенности использования метода вылавливания ошибок. Декодирование циклического кода путем вылавливания ошибок. Распознавание пакетов ошибок как особенность циклических кодов. Вычисление вектора ошибок.
доклад [20,3 K], добавлен 24.05.2012Разработка утилиты кодирования и декодирования формата Base 64 в программной среде Linux с использованием компилятора. Написание программы на языке С++. Кодирование символьной строки любого набора байт в последовательность печатных ASCII символов.
курсовая работа [1,4 M], добавлен 10.09.2013Симметричные и асиметричные методы шифрования. Шифрование с помощью датчика псевдослучайных чисел. Алгоритм шифрования DES. Российский стандарт цифровой подписи. Описание шифрования исходного сообщения асимметричным методом с открытым ключом RSA.
курсовая работа [101,1 K], добавлен 09.03.2009Типы, основные функции, элементы и принцип работы текстового редактора (компьютерной программы). Методы вставки внешних объектов в текст. Особенности текстового процессора Microsoft Word, его специальные возможности. Типовая структура интерфейса.
реферат [15,8 K], добавлен 07.12.2010Необходимые компоненты и порядок составления текстового редактора. Текст программы решения задачи на языке программирования C++. Контрольный пример работы текстового редактора. Создание и произведение операции форматирования простого документа.
курсовая работа [1,6 M], добавлен 03.09.2011Особенности управляющих микроконтроллеров. Разработка контроллера для реализации комплекса сбора информации, рассчитанного на фиксирование данных в оперативно-запоминающем устройстве и одновременную передачу её по GSM-каналу в виде SMS-сообщения.
курсовая работа [1019,3 K], добавлен 26.12.2012Внешнее исследование программного продукта, анализ кода, блок-схемы алгоритма модуля. Оценка качества защиты программы средствами статического и динамического исследования. Осуществление "мягкого" и "жесткого" взлома. Пути оптимизации механизмов защиты.
курсовая работа [1,3 M], добавлен 22.05.2016