[kosmor 0]

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

Решал в диссертации проблему сложности обработки ШПС сигналов с большой базой (более 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), на который можно наложить скремблирующую последовательность и сделать его шумоподобным.

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

[SKov 0]

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

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

Как вы пишите ниже, вы проверяли свой декодер в ДСК с переходной вероятностью 0.1.

Какой именно реальный канал (широкополосный , узкополосный или еще какой) стоит за этой моделью ДСК, и коду и декодеру глубоко фиолетово.

В типичной ситуации широкополосность никак не влияет на отношение сигнал/шум (если речь идет о АБГШ) и, вообще говоря, не имеет никакого отношения к дискретной модели канала, в котором работает декодер.

Что касается кодов максимальной длины (или другое название - эквидистантные коды), то для них все давно известно в смысле их декодирования.

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

Не верю, что на этом изъезженном вдоль и поперек месте можно было придумать что-то новое.

Скорее всего речь идет о переоткрытии чего-нибудь очень старого ;)

 

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

А это уже немножко странно. Ну, вам, как молодому аспиранту простительно не знать некоторые азы теории кодирования,

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

В этом смысле М-коды не очень хороши, т.к. имеют очень низкую скорость кода. А наибольшие ЭВК (в каналах со средним или слабым шумом) имеют корректирующие коды со скоростью в районе 3/4 (среди двоичных кодов).

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

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

 

Да... Тут лично мне тоже не все понятно. М-последовательности имеют плохой линейный профиль, поэтому редко используются в криптосистемах.

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

Жуть ! ;)

Изменено 3 июня, 2009 пользователем SKov

[kosmor 0]

SKov, спасибо за ответ из понимание. Я действительно молодой и неопытный аспирант :)

Внизу я уточнил информацию по теме.

 

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

Как вы пишите ниже, вы проверяли свой декодер в ДСК с переходной вероятностью 0.1.

Какой именно реальный канал (широкополосный , узкополосный или еще какой) стоит за этой моделью ДСК, и коду и декодеру глубоко фиолетово.

В типичной ситуации широкополосность никак не влияет на отношение сигнал/шум (если речь идет о АБГШ) и, вообще говоря, не имеет никакого отношения к дискретной модели канала, в котором работает декодер.

Что касается кодов максимальной длины (или другое название - эквидистантные коды), то для них все давно известно в смысле их декодирования.

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

Не верю, что на этом изъезженном вдоль и поперек месте можно было придумать что-то новое.

Скорее всего речь идет о переоткрытии чего-нибудь очень старого ;)

 

Есть два вида приема ШПС сигналов: прием в целом (демодулируется вся длина ШПС сигнала банком корреляторов) и посимвольный прием (каждый символ демодулируется отдельно, а потом в двоичном виде обрабатывается банком согласованных цифровых фильтров). Я рассматриваю второй вариант и модулицию BPSK. И моя задача снизить сложность цифровой обработки для длинных низкоскоростных кодов. В качестве ШПС я рассматриваю следующие псевдослучайные коды (ПСК): m-последовательности, коды Голда и Касами. Декодером я называю устройство, которое после приема всех двоичных символов ПСК, выдает решение о переданной информации. Таким образом, я работаю в дискретном канале, в котором аналогом АБГШ является ДСК. Каков реальный канал действительно не важно, но выжно то, что ПСК после модуляции обладает свойствами шумоподобных сигналов, которые трудно различимы энергетическим радиометром, а это важно в помехозащищенных системах для скрытности передачи. Также модулированные ПСК обладаются расширенным спектром, который затрудняет постановку искусственных помех: энергия таких помех либо размазывается по спектру сигнала (то есть уменьшается отношение сигнал/помеха), либо концентрируется в узкой полосе (тогда остаются чистые участки спектра). Таким образом, моя задача придумать алгоритм быстрого декодирования ПСК для борьбы именно с искусственными помехами. То есть модель ДСК, которую я используя для исследования корректирующей способности кода, это модель искусственных помех в некотором приближении.

 

Да, действительно один из кодов (то есть период m-последовательности) является эквидистантным. Если вам не сложно можете кинуть ссылку на какую нибудь литературу по алгоритмам декодирования эквидистантных кодов как обобщенных каскадных (по-моему есть книга Блоха Заблова Обобщенные каскадные кода, но не уверен что там упоминаются m-последовательности). В любом случае я не использую этот подход при декодирование и действительно, речь может идти о переоткрывании чего нибудь нового. Но я молодой и наивный :) Иду туда куда покажет руководитель :)

 

А это уже немножко странно. Ну, вам, как молодому аспиранту простительно не знать некоторые азы теории кодирования,

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

В этом смысле М-коды не очень хороши, т.к. имеют очень низкую скорость кода. А наибольшие ЭВК (в каналах со средним или слабым шумом) имеют корректирующие коды со скоростью в районе 3/4 (среди двоичных кодов).

 

В том то и дело, что ЭВК у моих кодов очень низкий! И несмотря на это руководитель продолжает утвержать, что я делаю, что-то гениальное :) Это понятно, что в обычных коммерческих системах наши коды не эффективны, но при борьбе с искусственными помехами по словам руководителя они вполне даже пригодны. Вот я хочу понять это действительно так?

 

Да... Тут лично мне тоже не все понятно. М-последовательности имеют плохой линейный профиль, поэтому редко используются в криптосистемах.

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

Жуть ! ;)

 

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

[SKov 0]

Есть два вида приема ШПС сигналов: прием в целом (демодулируется вся длина ШПС сигнала банком корреляторов) и посимвольный прием (каждый символ демодулируется отдельно, а потом в двоичном виде обрабатывается банком согласованных цифровых фильтров). Я рассматриваю второй вариант и модулицию BPSK. И моя задача снизить сложность цифровой обработки для длинных низкоскоростных кодов. В качестве ШПС я рассматриваю следующие псевдослучайные коды (ПСК): m-последовательности, коды Голда и Касами. Декодером я называю устройство, которое после приема всех двоичных символов ПСК, выдает решение о переданной информации. Таким образом, я работаю в дискретном канале, в котором аналогом АБГШ является ДСК. Каков реальный канал действительно не важно, но выжно то, что ПСК после модуляции обладает свойствами шумоподобных сигналов, которые трудно различимы энергетическим радиометром, а это важно в помехозащищенных системах для скрытности передачи. Также модулированные ПСК обладаются расширенным спектром, который затрудняет постановку искусственных помех: энергия таких помех либо размазывается по спектру сигнала (то есть уменьшается отношение сигнал/помеха), либо концентрируется в узкой полосе (тогда остаются чистые участки спектра). Таким образом, моя задача придумать алгоритм быстрого декодирования ПСК для борьбы именно с искусственными помехами. То есть модель ДСК, которую я используя для исследования корректирующей способности кода, это модель искусственных помех в некотором приближении.

Все-таки осталось в тумане, каким образом расширяется спектр сигнала за счет использования ПСК. Но, с другой стороны, вы подтвердили, что

после демодулятора имеете канал, который описывается как ДСК, и весь анализ эффективности кода проводится фактически для ДСК.

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

 

Да, действительно один из кодов (то есть период m-последовательности) является эквидистантным. Если вам не сложно можете кинуть ссылку на какую нибудь литературу по алгоритмам декодирования эквидистантных кодов как обобщенных каскадных (по-моему есть книга Блоха Заблова Обобщенные каскадные кода, но не уверен что там упоминаются m-последовательности). В любом случае я не использую этот подход при декодирование и действительно, речь может идти о переоткрывании чего нибудь нового. Но я молодой и наивный :) Иду туда куда покажет руководитель :)

Действительно, есть книжка Блоха-Зяблова, но ее лучше не читать ;) На ваше счастье, эквивалентом ОКК в данном случае является известная конструкция z = {x+y | y}, описанная, например в книжке МакВильямс и Слоэна.

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

 

В том то и дело, что ЭВК у моих кодов очень низкий! И несмотря на это руководитель продолжает утвержать, что я делаю, что-то гениальное :) Это понятно, что в обычных коммерческих системах наши коды не эффективны, но при борьбе с искусственными помехами по словам руководителя они вполне даже пригодны. Вот я хочу понять это действительно так?

Я пока тоже не понимаю ;)

[shasik 0]

Здесь слишком много букв, все прочитать не осилил.

Зацепила это фраза:

Оптимальный метод декодирования по методу максимального правдоподобия (МП) предполагает полный перебор всех 2^k разрешенных кодовых слов по n бит и сравнение со словом, принятым из канала. Поэтому сложность алгоритма МП растет экспоненциально с длиной кода, и его реализация требует большого объема памяти для хранения разрешенных слов.

 

Уже лет надцать как есть алгоритмы быстрого декодирования по методу максимального правдоподобия любых бинарных сигналов. Поэтому сложность будет расти не по exp, а N*log2(N).

[SKov 0]

Здесь слишком много букв, все прочитать не осилил.

Зацепила это фраза:

 

 

Уже лет надцать как есть алгоритмы быстрого декодирования по методу максимального правдоподобия любых бинарных сигналов. Поэтому сложность будет расти не по exp, а N*log2(N).

Это вы перепутали декодирование со сложностью сортировки массивов.

[kosmor 0]

Здесь слишком много букв, все прочитать не осилил.

Зацепила это фраза:

 

 

Уже лет надцать как есть алгоритмы быстрого декодирования по методу максимального правдоподобия любых бинарных сигналов. Поэтому сложность будет расти не по exp, а N*log2(N).

 

В книге Блоха Зяблова "Обобщенные каскадные коды", есть оценка сложности декодирования по методу максимального правдоподобия и синдромного декодирования, и на сколько я помню в одном случае сложность растет по эспоненте от длины кода, а в другом по экспоненте от длины информационного блока.

 

Все-таки осталось в тумане, каким образом расширяется спектр сигнала за счет использования ПСК. Но, с другой стороны, вы подтвердили, что

после демодулятора имеете канал, который описывается как ДСК, и весь анализ эффективности кода проводится фактически для ДСК.

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

Расширение спектра достигается за счет того, что вместо передачи некодированных информационных k битов за время T, по каналу передается n чипов ПСК за то же время T, то есть скорость передачи чипа ПСК равна Tch = T/R, где R = n/k. В этом случае, если я правильно понимаю, при использованиии БФМ модуляции достигается выигрыш от обработки или по другому коэффициент прямого расширения спектра равный WT = n.

 

Действительно, есть книжка Блоха-Зяблова, но ее лучше не читать ;) На ваше счастье, эквивалентом ОКК в данном случае является известная конструкция z = {x+y | y}, описанная, например в книжке МакВильямс и Слоэна.

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

Спасибо за очень ценную информацию!

[SKov 0]

В книге Блоха Зяблова "Обобщенные каскадные коды", есть оценка сложности декодирования по методу максимального правдоподобия и синдромного декодирования, и на сколько я помню в одном случае сложность растет по эспоненте от длины кода, а в другом по экспоненте от длины информационного блока.

 

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

Самая простая - min {R,(1-R)}, где R- кодовая скорость - это , видимо, то, что вы вспомнили.

Дальше было много улучшений типа R*(1-R)/2 и др. Что там последнее на сегодняшний день - не могу сказать, последние

несколько лет не следил за периодикой. Однако ни о какой неэкспоненциальной сложности речи не может идти.

Есть класс кодов (низкоплотностные коды Галлагера), для которых известны алгоритмы декодирования

со сложностью порядка n*log(n), но там речь не идет о МП, а просто исправляются ошибки веса до ненулевой

доли от кодовой длины. Где-то я, кажется, видел работу, в которой доказано, что вообще задача

декодирования произвольного (длинного) кода по МП есть NP-полная задача.

 

 

Кстати, я припоминаю, что для ваших кодов имеются алгоритмы декодирования (по МП или до мин. расст. -точно не помню) со сложностью n*log(n).

Но для асимптотики этот случай не интересный, т.к. кодовая скорость стремится к нулю.

[kosmor 0]

Кстати, я припоминаю, что для ваших кодов имеются алгоритмы декодирования (по МП или до мин. расст. -точно не помню) со сложностью n*log(n).

Но для асимптотики этот случай не интересный, т.к. кодовая скорость стремится к нулю.

 

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

[SKov 0]

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

Напишите свой мейл, как найду в архиве что-то на эту тему, напишу.

[kosmor 0]

Напишите свой мейл, как найду в архиве что-то на эту тему, напишу.

 

Отправил вам личным сообщением свой почтовый ящик.

[shasik 0]

Это вы перепутали декодирование со сложностью сортировки массивов.

Скажу честно, я не понял о чем Вы.

Я говорил, про декодирование, а при чем здесь сортировка массивов я не знаю.

 

В книге Блоха Зяблова "Обобщенные каскадные коды", есть оценка сложности декодирования по методу максимального правдоподобия и синдромного декодирования, и на сколько я помню в одном случае сложность растет по эспоненте от длины кода, а в другом по экспоненте от длины информационного блока.

На заборе тоже пишут.

Еще раз.

Если свести декодирование по методу МП к умножению принятой реализации на сигнальную матрицу и нахождению максимума, то сложность такого метода для бинарных сигналов N*log2(N), где N - длина сигнала.

Быстрый алгоритм умножения вектора на матрицу основан на факторизации сигнальной матрице, а факторизовать можно любую бинарную матрицу без всяких условий на вид сигнала (функции Уолша, m-последовательность, КВ-коды и т.п.)

[SKov 0]

На заборе тоже пишут.

Это вы зря. Книга Блоха и Зяблова хоть и написана туманно,

но очень уважаема в среде специалистов. Как и авторы этой книги.

А относительно ваших утверждений о сложности декодирования,

то ситуация мне напоминает известную рекламу со словами "А мужики-то не знают..."

Думаю, что все дело в разном понимании постановки задачи или в разной методике оценки сложности.

Если у вас есть ссылки на работы, где изложен ваш подход к декодированию,

с удовольствием взгляну, как будет свободное время.

[shasik 0]

Это вы зря. Книга Блоха и Зяблова хоть и написана туманно,

....

Если у вас есть ссылки на работы, где изложен ваш подход к декодированию,

с удовольствием взгляну, как будет свободное время.

Про качество книги я не рассуждал. На заборах тоже иногда правду пишут, только нужно "правильно" читать.

 

Книги у меня на домашнем компе, смогу выложить только в понедельник.

Сами можете поискать работы Лосева, Мальцева и Богуша, Абламейко и др.

 

ЗЫЖ Из книг можно еще вспомнить достаточно толковую

"Поиск и декодирование сложных дискретных сигналов" (Лосев Бродская Коржик 1988)

 

ЗЗЫЖ А можем и поэкспериментировать: Вы мне бинарную матрицу, а я Вам - ее факторизацию.

[kosmor 0]

Про качество книги я не рассуждал. На заборах тоже иногда правду пишут, только нужно "правильно" читать.

 

Книги у меня на домашнем компе, смогу выложить только в понедельник.

Сами можете поискать работы Лосева, Мальцева и Богуша, Абламейко и др.

 

ЗЫЖ Из книг можно еще вспомнить достаточно толковую

"Поиск и декодирование сложных дискретных сигналов" (Лосев Бродская Коржик 1988)

 

ЗЗЫЖ А можем и поэкспериментировать: Вы мне бинарную матрицу, а я Вам - ее факторизацию.

 

Скорее всего, как и писал SKov, дело тут в разных подходах в оценке сложности. Есть такой подход который рассматривает различные коды с одинаковой скоростью r = k/n, и считается что тот алгоритм оптимальнее по сложности, у которого рост сложности медленне относительно n.

Матрица, про которую вы писали, скорее всего имеет размерность n строк на (2^k) = (2^(r*n)) столбцов, поэтому есть основание полагать сложность ее обработки растет как (2^(r*n)), то есть экспоненциально, если r считать константой. Поправьте меня, если я что не так написал :)