Введение к работе
-3-
Актуальность темы диссертации. Улучшение качественных пока-телей систем передачи дискретных сообщений возможно при пользовании помехозащитных кодов, блоковых или сверточных. Вве-ние избыточности обусловливает дополнительное увеличение меж-мвольных искажений (радиоканалы с рассеянием и каналы с ограни-нной полосой пропускания). Межсимвольная интерференция (МСИ) жет быть введена преднамеренно для получения требуемых спект-льных свойств сигнала-. Оптимальная обработка кодированных сиг-лов на выходе канала с межсимвольной интерференвдей в условиях здействия аддитивных помех требует значительных вычислительных грат и объемов памяти, увеличивающихся с ростом помехозащитных эйств кодов и длины импульсной реакции канала.
Актуальной для исследования в настоящее время является пробна синтеза алгоритмов обработки, экономных в вычислительном ношении и приемлемых по требуемому объему памяти. Алгоритм Ви-5би обладает рядом достоинств, но из-за экспоненциального уверения вычислительных затрат и необходимого объема памяти с рос-4 размерности задачи (длины кодового ограничения сверточного ja(CK), длины импульсного отклика модулятора или канала связи, шчества проверочных символов в кодовом слове блочного кода \)) неприменим к задачам большой размерности. Указанное ограни-эие на размерность задач сдерживает рост качественных показате-) систем передачи дискретных сообщений. Сложность алгоритмов юдирования удается уменьшить, используя коды со специальной >уктурой (например, декодирование кодов БЧХ и мажоритарное де-[ирование ).
В общем случае сокращения вычислительных затрат и необходи-о объема памяти можно добиться, применяя алгоритмы с более жной логической структурой. Примерами таких алгоритмов могут жить процедуры последовательного декодирования. Преимущества оритмов со сложной структурой в полной мере проявляются при граммной реализации. Их практическое применение сдерживалось утствием подходящей элементной базы. Положение радикальным азом изменилось с появлением однокристальных сигнальных Прохоров с высокой тактовой частотой (до 40 МГц), большим адрес-пространством памяти (до 4 Гбайт), гибкой универсальной архи-гурой и соответствующим набором команд.
-4- ,
Цель диссертационной работы состоит в разработке на осної методов комбинаторной оптимизации алгоритмов приема дискретні сообщений с уменьшенными вычислительными затратами и необходим; объемом памяти.
Основными задачами работы, определяемыми поставленной целы являются: синтез алгоритмов приема дискретных сообщений с умен шенными требованиями к вычислительной мощности процессора и объ му памяти, оценка характеристик разработанных алгоритмов путем моделирования на ЭВМ.
Методы исследования основаны на использовании статистичесу теории связи, комбинаторной оптимизации, теории алгоритмичео сложности задач. В работе применяются аппараты теории множес линейной алгебры, теории вероятностей и моделирование на ЭВМ.
Научная новизна. В диссертации задача приема дискрет] сообщений рассматривается как задача отыскания экстремума фу: ции, заданной на конечном множестве, и для ее решения использу ся методы комбинаторной оптимизации.
Рассмотрены различные методы дискретной оптимизации (ме решения псевдобулевых неравенств, метод ветвей и границ и близ к нему метод последовательного декодирования, метод решения, с занный с отысканием минимального разреза в транспортной се применительно к различным задачам приема дискретных сообщений.
В диссертации показано, что алгоритмы Витерби и Волз стек-алгоритм и первая версия creeper-алгоритма с метрикой маг пального правдоподобия могут быть рассмотрены в рамках ме' ветвей и границ.
Использование методов дискретной оптимизации позволило п чить ряд алгоритмов приема дискретных сообщений, превосход известные по показателям вычислительной сложности, необходи объему памяти, помехоустойчивости, вероятности отказа при огр чении на время вычислений и объем памяти:
метод динамического программирования (алгоритм Вите распространен на решение задачи декодирования линейного БК использовании решетчатых сигналов (PC)і описана проц< построения объединенной решетки Витерби-Вольфа, применение ] рой позволяет решать указанную задачу;
разработан алгоритм мягкого декодирования линейных основанный на процедуре отыскания базисных решений линейных добулевых неравенств;
- на основе метода ветвей и границ разработан алгоритм поис-
глубину с порогом (ПГП) для приема PC;
- разработана процедура генерации дерева кодовых комбинаций
ее основе построен алгоритм ПГП для мягкого декодирования
Зных БК (или СК с нейтрализацией хвостов, если они рассматри-
:я как БК); показано, что усеченные версии данного алгоритма
известные алгоритмы декодирования Л.Ф. Бородина и А.С. Нау-
разработаны алгоритмы последовательного декодирования для ма PC и мягкого декодирования линейных БК, использующие идео-о алгоритма Фано и некоторые компоненты метода ветвей и гра-
на основе алгоритма отыскания минимального разреза в спортной сети разработан алгоритм демодуляции в канале с МСИ некоторых ограничениях на вид импульсной реакции.
Получена рекуррентная форма алгоритма полного перебора с обой связью по решению (алгоритма Кловского-Николаева) для ма PC.
Разработан алгоритм оптимального поветвевого приема PC, поший обобщением рекуррентного алгоритма Абенда и Фритчмена імальной, поэлементной демодуляции в канале с МСИ.
Практическая ценность работы. Полученные результаты имеют ладную направленность и дают возможность улучшить характерис-і систем передачи дискретных сообщений:
а) при заданном методе модуляции и кодирования уменьшить
шость обработки на приемной стороне;
б) при заданной сложности устройства обработки на приемной
»не использовать более мощный метод модуляции и кодирования,
шечивающий повышение помехоустойчивости, или увеличить ско-
иь.передачи информации, или вместо субоптимального алгоритма
іботки использовать оптимальный.
Предложенные алгоритмы позволяют уменьшить сложность уст-:тв обработки (вычислительные затраты и необходимый объем nail , обеспечивают возможность обмена вычислительной сложности необходимый объем памяти при решении следующих задач: декоди-ание СК и сигнально-кодовых конструкций (СКК) на их основе, эдуляция сигналов с частичным откликом, демодуляция в канале с , мягкое декодирование линейных БК или СК с нейтрализацией зтов, любые комбинации перечисленных задач. Полученные алго-
ритмы не накладывают ограничений на алгебраическую стру используемых кодов, кроме требования линейности, т.е. явд универсальными.
Результаты работы расширяют возможности разработчиков ройств приема дискретных сообщений, реализуемых програмні; диссертации приведены исчерпывающе описания разработанных ритмов, что позволяет переводить их непосредственно в прог для сигнальных процессоров. Сигнальные процессоры постав7 вместе с компиляторами языка СИ, на котором предложенные алг мы реализованы при моделировании. Указанное обстоятельство дельно упрощает перенос разработанных алгоритмов на сигне процессоры.
Предложенные алгоритмы и, в частности, алгоритм ПГБ незначительной модификации могут найти применение для иссле ния на ЭВМ дистанционных свойств систем сигналов, линейных и СКК на их основе.
Реализация результатов работы. Часть результатов диссе^ отражена в отчетах по госбюджетным и хоздоговорным НИР, выпс ным в Отраслевой научно-исследовательской лаборатории "Ср эффективной передачи сообщений по каналам связи" Поволжскогс статута информатики, радиотехники и связи.
Апробация работы. Результаты работы докладывались и обе лись на Всесоюзной конференции по теории кодирования (г. 0; 1988), на научно-технических конференциях профеесс преподавательского состава и научных сотрудников ПИИРС, на них семинарах кафедры теоретических основ радиотехники и ІШИРС (1987vl993).
Публикации. По теме диссертации автором опубликовано 1J бот, в том числе 3-й изобретения.
Структура и объем работы. Диссертационная работа состої введения, шести глав, заключения и списка литературы, включг 139 наименований. Она содержит 201 страницу машинописного т< 46 страниц рисунков, 3 страницы таблиц.
Похожие диссертации на Исследование методов сокращения вычислительных затрат в алгоритмах приема дискретных сообщений
