Помехоустойчивые ШПС коды, Помогите определить практическую ценность нового алгоритма Опции

[КонстантинТКС]

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

Решал в диссертации проблему сложности обработки ШПС сигналов с большой базой (более 1000 чипов). В процессе исследования получили быстрый алгоритм декодирования (БДК), который позволяет декодировать блочный циклический код (n= 1023, k = 10, dmin = 512), образованный различными циклическими сдвигами периода бинарной m-последовательности с памятью 10 (период 1023 чипа). Оптимальный метод декодирования по методу максимального правдоподобия (МП) предполагает полный перебор всех 2^k разрешенных кодовых слов по n бит и сравнение со словом, принятым из канала. Поэтому сложность алгоритма МП растет экспоненциально с длиной кода, и его реализация требует большого объема памяти для хранения разрешенных слов. Это затрудняет техническую реализацию метода МП и близких к нему (посимвольный прием на банк корреляторов или согласованных фильтров, быстрые преобразования матриц Адамара) при обработке длинных кодов (с базой более 1000). Полученный нами алгоритм БДК позволяет декодировать со сложностью, которая растет почти линейно с длиной кода и не требует памяти для хранения всего кодового блока и разрешенных слов.

Значительное снижение сложности алгоритма было достигнуто за счет ухудшения исправляющей способности кода. Так, например, применительно к коду (1023,10) алгоритм МП позволяет достичь вероятности ошибки на блок Q=10^-5 при вероятности ошибки на символ q= 0.195 в дискретном симметричном канале. Таких же результатов алгоритм БДК достигает при q=0.1. И что самое интересное, простое повторение информационного блока из 10 бит 101 раз с дальнейшим мажоритарным декодированием, то есть блочный код (1010, 10), достигает таких же результатов при =0.276. Последнее обстоятельство ставит лично для меня под сомнение целесообразность использования ШПС кодов в качестве помехоустойчивых кодов. И действительно, редко встретишь в литературе упоминание о таком использовании. Практически везде ШПС коды используют для кадровой синхронизации и для расширения спектра. А потребность в обработке ШПС кодов с большой базой в основном возникает при разработке помехозащищенных военных систем для борьбы с преднамеренными помехами противника. Это связано с тем, что энергетическая скрытность ШПС сигнала растет с увеличением базы. Но в этом случае ШПС коды используются для повторной модуляции сигнала в целях расширения спектра, то есть передающая и принимающая сторона знают о некоторой одной ШПС последовательности, которая накладывается и снимается с информационного сигнала. Значит, ШПС код модулирует, а не кодирует информационную последовательность, и поэтому не может рассматриваться как помехоустойчивый код.

Руководитель предлагает использовать длинные ШПС коды в помехозащищенных системах в качестве корректирующих кодов с хорошей энергетической скрытностью для борьбы с узкополосными и широкополосными искусственными помехами. Я никак не могу понять целесообразность в этом. Во-первых, известно, что m-последовательности обладают очень низкой структурной скрытностью, и для ее распознавания достаточно набрать 2*m безошибочных чипов, где m – память последовательности. Следовательно, велика вероятность перехвата сигнала противником. Во-вторых, почему бы, например, для кодирования не выбрать более эффективный код и может быть даже с меньшей избыточностью (намного меньшей, чем в нашем случае R= n/k = 102), на который можно наложить скремблирующую последовательность и сделать его шумоподобным.

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

[samurad]

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

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

Решал в диссертации проблему сложности обработки ШПС сигналов с большой базой (более 1000 чипов). В процессе исследования получили быстрый алгоритм декодирования (БДК), который позволяет декодировать блочный циклический код (n= 1023, k = 10, dmin = 512), образованный различными циклическими сдвигами периода бинарной m-последовательности с памятью 10 (период 1023 чипа). Оптимальный метод декодирования по методу максимального правдоподобия (МП) предполагает полный перебор всех 2^k разрешенных кодовых слов по n бит и сравнение со словом, принятым из канала. Поэтому сложность алгоритма МП растет экспоненциально с длиной кода, и его реализация требует большого объема памяти для хранения разрешенных слов. Это затрудняет техническую реализацию метода МП и близких к нему (посимвольный прием на банк корреляторов или согласованных фильтров, быстрые преобразования матриц Адамара) при обработке длинных кодов (с базой более 1000). Полученный нами алгоритм БДК позволяет декодировать со сложностью, которая растет почти линейно с длиной кода и не требует памяти для хранения всего кодового блока и разрешенных слов.

Как следует из дискуссии, скорость вашего алгоритма равна n*log(n), что равно известным "быстрым" методам декодирования, которые я изучал в своей диссертации. Однако у меня был другой критерий сравнения: не исправление какого-то числа ошибок демодуляции, а средняя скорость вхождения в синхронизм (acquisition) при заданной вероятности правильного вхождения.

Значительное снижение сложности алгоритма было достигнуто за счет ухудшения исправляющей способности кода. Так, например, применительно к коду (1023,10) алгоритм МП позволяет достичь вероятности ошибки на блок Q=10^-5 при вероятности ошибки на символ q= 0.195 в дискретном симметричном канале. Таких же результатов алгоритм БДК достигает при q=0.1. И что самое интересное, простое повторение информационного блока из 10 бит 101 раз с дальнейшим мажоритарным декодированием, то есть блочный код (1010, 10), достигает таких же результатов при =0.276. Последнее обстоятельство ставит лично для меня под сомнение целесообразность использования ШПС кодов в качестве помехоустойчивых кодов.

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

Руководитель предлагает использовать длинные ШПС коды в помехозащищенных системах в качестве корректирующих кодов с хорошей энергетической скрытностью для борьбы с узкополосными и широкополосными искусственными помехами. Я никак не могу понять целесообразность в этом. Во-первых, известно, что m-последовательности обладают очень низкой структурной скрытностью, и для ее распознавания достаточно набрать 2*m безошибочных чипов, где m – память последовательности. Следовательно, велика вероятность перехвата сигнала противником. Во-вторых, почему бы, например, для кодирования не выбрать более эффективный код и может быть даже с меньшей избыточностью (намного меньшей, чем в нашем случае R= n/k = 102), на который можно наложить скремблирующую последовательность и сделать его шумоподобным.

Когда говорят о энергетической скрытности, то обычно имеют в виду энергетику (С/Ш) символа на выходе передатчика. Структурная избыточность здесь второстепенный фактор - если принятый код имеет много ошибок, то никакая структурная извыточноть вплоть до примитивного повторения не поможет его правильно дешифровать.

Тем не менее, то что вы говорите о скремблировании - толковый и уже распространенный метод, напр. в сотовых системах связи 3G.

В этой связи хотел бы обратить ваше внимание на посимвольный прием, который вы используете. Такой прием фундаментально и серьезно уступает приему в целом (напр., корреляция всего периода ШПС) с точки зрения энергетической скрытности, особенно в многоканальных системах.

Простой пример: GPS сигнал на входе навигационного приемника - типичный многоканальный CDMA сигнал. Этот сигнал фактически "похоронен" в шуме, т.е. невидим до той поры, пока он не будет коррелирован с местной копией, и так по каждому спутнику. (Для правильной навигации, впрочем, достаточно успешно декодировать один из GPS спутников, чтобы прочитать из навиг. сообщения, какие коды "видны" в данный момент. Если бы количество используемых кодов каждым спутником было бы велико, то GPS можно было бы по праву считать системой с высокой энергетической скрытностью.) Если попробовать сначала принять каждый символ принятого кода, напр., согласованным фильтром, а потом делать корреляцию результата, то для правильной демодуляции всего сообщения потребуется значительно более высокий С/Ш символа (при одинаковой вероятности ошибки сообщения) из-за его более пологой корреляционной функции. Кроме того, "дружественные" помехи по соседним кодовым каналам еще поднимут требуемый С/Ш символа.

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

[КонстантинТКС]

samurad, огромное спасибо за ответ! Чувствуется, что вы действительно в теме

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

Да это на самом деле так - осталось два месяца до конца аспирантуры и проделана большая работа. Есть альтернативная тема, но времени, чтобы ее оформить совсем нет.

Как следует из дискуссии, скорость вашего алгоритма равна n*log(n), что равно известным "быстрым" методам декодирования, которые я изучал в своей диссертации. Однако у меня был другой критерий сравнения: не исправление какого-то числа ошибок демодуляции, а средняя скорость вхождения в синхронизм (acquisition) при заданной вероятности правильного вхождения.

Быстрые методы, которые вы изучали, требовали хранить в памяти все циклические сдвиги m-последовательности, то есть полный набор разрещенных кодовых слов?
И какой метод синхронизации вы использовали?

Когда говорят о энергетической скрытности, то обычно имеют в виду энергетику (С/Ш) символа на выходе передатчика. Структурная избыточность здесь второстепенный фактор - если принятый код имеет много ошибок, то никакая структурная извыточноть вплоть до примитивного повторения не поможет его правильно дешифровать.

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

В этой связи хотел бы обратить ваше внимание на посимвольный прием, который вы используете. Такой прием фундаментально и серьезно уступает приему в целом (напр., декорреляции) с точки зрения энергетической скрытности.
Простой пример: GPS сигнал на входе навигационного приемника - типичный многоканальный CDMA сигнал.
Этот сигнал фактически "похоронен" в шуме, т.е. невидим до той поры, пока он не будет декоррелирован, и так по каждому спутнику. (Для правильной навигации, впрочем, достаточно успешно декодировать один из спутников, чтобы прочитать из навиг. сообщения, какие коды "видны" в данный момент. Если бы количество используемых кодов каждым спутником было бы велико, то GPS можно было бы по праву считать системой с высокой энергетической скрытностью.)
Если попробовать сначала принять каждый символ какого-то кода, напр., согласованным фильром, а потом делать декорреляцию, то для правильной демодуляции потребуется значительно более высокий С/Ш символа.

Если я не ошибаюсь, разница между приемом в целом и посимвольным приемом составляет 2 дБ. Но при очень большой длине ШПС сигнала более (1000), возникают серьезные трудности при обработке в целом, то есть либо не хватает аппаратных ресурсов для реализации декорреляции, либо декоррелятор не успевает из-за своей сложности обрабатывать канальные потоки. Поэтому в таких случаях переходят на посивмольный прием.

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

К сожалению, я могу лишь показать насколько снизилась вычислительная и сложность технической реалиции по отношению к другим быстрым алгоритмам (например Быстрое преобразование матриц Адамара) и на сколько при этом ухудшилась энергетика. То есть выигрыш по сложности был достигнут за счет ухудщения в энергетике. Например при вероятности блоковой ошибки 10^-5 замена декодера максимального правдоподобия на декодер БДК требует повышения отношения сигнал/шум на 3.4679 дБ.

[samurad]

Быстрые методы, которые вы изучали, требовали хранить в памяти все циклические сдвиги m-последовательности, то есть полный набор разрещенных кодовых слов?
И какой метод синхронизации вы использовали?

Метод с памятью на все циклические сдвиги, т.е. метод максимального правдоподобия (МП) оптимальный по вероятности ошибочного приема m-последовательности, использовался как один из сравниваемых методов, точнее, как точка отчета вычислительной сложности при минимальном времени синхронизации. Расматривались и другие, суб-оптимальные методы, не требующие такой большой памяти, но требующие большего времени на синхронизацию. Насколько я помню, большинство суб-оптимальных методов, разновидности мажоритарного или комбинационного кодирования (внеший код модулирует внутренний) требуют очень мало памяти, но серьезно проигрывают МП в энергетике , т.к. сильно зависят от посимвольного приема, и в результате медленно работают или совсем не работают при малых С/Ш.

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

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

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

Да, постороний наблюдатель может видеть только символы ШПС, а их энергетика очень мала.

Если я не ошибаюсь, разница между приемом в целом и посимвольным приемом составляет 2 дБ. Но при очень большой длине ШПС сигнала более (1000), возникают серьезные трудности при обработке в целом, то есть либо не хватает аппаратных ресурсов для реализации декорреляции, либо декоррелятор не успевает из-за своей сложности обрабатывать канальные потоки. Поэтому в таких случаях переходят на посивмольный прием.

Разница в энергетике между приемом в целом и посимвольным приемом зависит от используемого метода модуляции и демодуляции: может быть близка к нулю, а может быть много больше 2 дБ.

Сейчас 1000 не является большой длиной ШПС. Уже выпускаются микросхемы, в частности для GPS, где размещены сотни тысяч корреляторов для кодов GPS L1 C/A длиной 1023 чипа. Да, и если период последовательности непростой, то достаточно хранить только составляющие последовательности короткой длины. Для криптозащиты такие коды в "голом" виде представляются как слабозащищенные. Однако, их легко можно привести к высокой линейной сложности без дополнительных потерь на время синхронизации, "упаковав" их в нелинейную функцию или каскадированием (GMW коды).

К сожалению, я могу лишь показать насколько снизилась вычислительная и сложность технической реалиции по отношению к другим быстрым алгоритмам (например Быстрое преобразование матриц Адамара) и на сколько при этом ухудшилась энергетика. То есть выигрыш по сложности был достигнут за счет ухудщения в энергетике. Например при вероятности блоковой ошибки 10^-5 замена декодера максимального правдоподобия на декодер БДК требует повышения отношения сигнал/шум на 3.4679 дБ.

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

Кстати, а где вы защищаетесь, если не секрет?