DATA TRANSMISSION DEVICE BASED ON CODES WITH LOW DENSITY OF CHECKS ON PARITY
Устройство передачи данных на основе кодов с низкой плотностью проверок на четность

Изобретение относится к области теории кодирования, в частности к системам для объединенного кодирования с исправлением и обнаружением ошибок с целью повышения эффективности использования спектра при передаче данных в цифровой системе радиосвязи.
Актуальной является задача не только исправление ошибок при канальном кодировании, но и обнаружения неисправленных ошибок и организация автоматического запроса повторения (АЗП) с целью исправить подобные ошибки за счет дополнительной передачи минимально возможного числа кодовых символов. Основной характеристикой помехоустойчивого кодирования является скорость кодирования  равная отношению число информационных символов к кодовым, поскольку кодирование вносит избыточность, скорость кодирования .
Широко известен параллельный сверточный турбокод [Berrou C. Near Shannon limit error – correcting coding and decoding / C. Berrou, A. Glaviex, P. Thitimajshina // IEEE International Communications Conference: Proc. 1993. – Geneva (Switzerland), 1993. – P. 1064–1070], позволивший приблизиться к потенциально достижимым характеристикам помехоустойчивого кодирования. Способ характеризуется следующим. На вход первого кодера подается информационная последовательность, на вход второго подается та же последовательность, но после перемежителя. Тем самым достигается статистическая независимость, особенно при больших размерах кодового блока. Итеративный подход заключается в том, что результаты одного декодирования с мягким выходом могут использоваться при другом декодировании, как априорная информация. Однако турбокод не является более эффективным, чем сверточный код, декодируемый по алгоритму Витерби, при размере фрейма менее 200 бит.
Аналогом заявляемого способа является продукт фирмы Trellis Ware код F-LDPC [Halford, Thomas & Bayram, Metin & Kose, Cenk & M. Chugg, Keith & Polydoros, Andreas. (2008). The F-LDPC Family: High-Performance Flexible Modern Codes for Flexible Radio. 376 - 380. 10.1109/ISSSTA.2008.75.]. Достоинством этого решения является глубокая интеграция протокола автоматического запроса повторной передачи (АЗП) с алгоритмом помехоустойчивого кодирования. Утверждается, что решение обладает максимально гибкими возможностями, одно ядро кодер/декодер поддерживает 40 кодовых скоростей (1/2–32/33) при этом допустимые размеры фрейма: 128, 256, 512, …, 16384 бит. Однако, например, для голосовых данных, размеры фреймов, производимые вокодером, могут составлять 16, 40, 80, 172 бита, таким образом невозможность работать с блоками от 20 бит является недостатком кода F-LDPC.
Классическая АЗП (ARQ), которая при ошибочном декодировании кадра предусматривает стирание принятых данных, полную повторную передачу кадра и независимое декодирование вновь полученного кадра не эффективна, т.к. приводит к слишком большой избыточной передаче данных. В настоящее время все большое распространение получает гибридная повторная передача [Error Control Coding: Fundamentals and Applications/ S. Lin, D. J. Costello, Jr.  – NJ: Englewood Cliffs. – 1983. – 603 p.]. Суть метода в том, что более эффективной является такая стратегия, которая предусматривает при ошибочном декодировании сохранение данных кадра, получение от передатчика некоторой дополнительной информации, и повторное декодирование кадра с использованием этой дополнительной информации. Если объем дополнительной информации меньше объема целого кадра, то эффективность использования канала связи существенно увеличивается. Данный подход исследован Хагенауэром [J. Hagenauer. Rate Compatible Punctured Convolutional Codes (RCPC Codes) and their Applications. // IEEE Trans. Commun. – Vol. 36. – Apr. 1988. – P. 389-400.] и Чейзом [D. Chase. Code Combining  A MaximumLikelihood Decoding Approach for Combining an Arbitrary Number of Noisy Packets. // IEEE Trans. Comm. – Vol. 33. – May 1985. – P. 385393] с разных позиций.
Рассмотрим классификацию рассмотренных схем АЗП (ARQ):
• Гибридная АЗП Типа 1 (НARQ-1 – суммирование Чейза). Данная стратегия повторной передачи характеризуется тем, что повторно передается тот же самый кадр.
• Гибридная АЗП Типа 2 (НARQ-2 – наращивание избыточности). Данная стратегия повторной передачи характеризуется тем, что число бит для повторной передачи меньше, чем в исходном кадре. Копия для повторной передачи не может быть декодируема самостоятельно.
• Гибридная АЗП Типа 3 (НARQ-3). Копия для повторной передачи может декодироваться самостоятельно. Однако кадр для повторной передачи может отличаться от первоначально переданного кадра, то есть может быть закодирован другим кодом.
Данную классификацию можно обобщить следующим образом:
• АЗП (ARQ) с полной передачей (к ней относится Тип 1 и Тип 3).
• АЗП (ARQ) с частичной передачей (Тип 2).
Темой дальнейшего исследования будет частичная передача – гибридная АЗП типа 2 (HARQ-2).
Возможны несколько подходов к реализации подобной стратегии АЗП (ARQ):
1. Повторная передача части ранее переданных кодовых символов кадра и их оптимальное сложение с кодовыми символами, сохраненными в памяти приемника.
2. Использование кодов с нарастающей сложностью. В случае ошибочного декодирования на передающей стороне вычисляются новые (дополнительные) проверочные символы, которые передаются приемнику.
Известен способ [Пат. 2427491 CA (0237743 WO), МКИ H04L1/18. Automatic Request Protocol Based Packet Transmission Using Punctured Codes / R. Wang, Ming J., A. Garmonov, A. Savinkov, A. Zhdanov. –PST Gazette. – 2002, May 19. – P. 9340], где подобная стратегия не приводит к снижению пропускной способности поскольку дополнительные кодовые символы или частичную повторную передача передают в составе следующего пакета, где проводят дополнительное перфорирование, освобождая место для проверочных кодовых символов для пакета в котором обнаружена ошибка, таким образом, ошибка в одном пакете исправляется за счет избыточности другого.
В классе линейных блоковых кодов можно особо выделить подкласс кодов с низкой плотностью проверок на четность [Gallager R. “Low Density Parity Check Codes”// MIT Press 1963], превосходящий по своим характеристикам турбокод. Особенностью данного кода является наличие простой графической модели алгоритма декодирования, определяемого как декодирование на графе (фиг. 1). Декодирование на графе следует понимать в том смысле, что граф определяет разбиение всего кодового слова на более короткие коды, причем короткие коды могут перекрываться друг с другом. Избежать данных перекрытий можно путем повторения перекрывающихся кодовых символов. Разные копии принятого кодового символа или мягкого решения об этом символе входят в различные кодовые слова более короткого кода, при этом все кодовые слова короткого кода могут быть декодированы независимо. Такая структура может быть представлена в виде двудольного графа один тип вершин, которого ассоциирован с кодовыми символами, причем количество ребер, исходящих из каждой вершины соответствует количеству повторений кодового символа (переменная вершина – обозначена прямоугольником). Другой тип вершин соответствует коротким кодам, причем каждая вершина есть кодовое слово с количеством кодовых символов равным числу входящих ребер (проверочная вершина – обозначена кругом). Каждой проверочной вершине может быть приписана контрольная сумма, как индикатор наличия ошибок в коротком коде. Переменные вершины могут быть соединены только с проверочными вершинами, и, наоборот, проверочные вершины могут быть соединены только с переменными вершинами, что позволяет рассматривать граф как двудольный.
Такой двудольный граф называют графом Таннера [Tanner R.M. A Recursive Approach to Low Complexity Codes / R.M. Tanner // IEEE Transaction on Information Theory. – 1981. –Vol. IT27, № 9. – P. 533547]. По сути, для линейного блокового кода, граф Таннера является графическим представлением проверочной матрицы. Безошибочное декодирование характеризуется равенством нулю всех контрольных сумм – кодовых ограничений.
Код с низкой плотностью проверок на четность может быть декодирован в мягких решениях, используя алгоритм обмена сообщений (фиг. 1). Алгоритм обмена сообщениями [Gallager R. “Low Density Parity Check Codes”// MIT Press 1963] инициализируют каждый переменную вершину информацией о достоверности приема каждого символа (мягким решением), полученной из канала.
1. Вычисляют значение исходящего сообщения от переменной вершины равного апостериорной вероятности для кодового символа принять определенное значение кодового символа, отнесенного к этому переменной вершине для каждого ребра двудольного графа.
2. В каждом проверочной вершине модифицируют исходящие сообщения от тех переменных вершин, с которым они связаны ребром двудольного графа, и для которого они являются входящими, ставя в соответствие каждому ребру исходящие сообщения проверочной вершине, которые равны второму набору вероятностей для кодового символа принять определенное значение.
3. Обновляют исходящие сообщение переменной вершине входящими сообщениями, которые являются исходящими сообщениями проверочной вершине.
4. Повторяют итерации определенное число раз или до тех пор, пока кодовые ограничения не будут выполнены.
Знак исходящего сообщения выбирают таким, чтобы удовлетворить кодовым ограничениям. Абсолютное значение исходящего сообщения вычисляют при помощи функции . Эта функция является решающей функцией или логарифмом отношения правдоподобия. Функция обладает коммутативностью:
Есть несколько методов для определения функции . Наиболее простой известен как алгоритм “min-sum”. Абсолютное значение исходящего сообщения равно минимальному абсолютному значению среди входящих сообщений за исключением сообщения от той вершины, для которого предназначено данное исходящее сообщение:
Другой метод задания функции  состоит в определении функции через функцию , применяемую в LOG MAP алгоритме [Pietrobon S.S. Implementation and Performance of a Turbo/MAP Decoder / S.S. Pietrobon // International J. of Satellite Communication. – 1998. Vol. 16 (Jan-Feb). – P. 23-46]. Функция может быть задана как:
Где функция , может быть представлена в виде таблицы.
Существует модификация предложенного метода, где дополнительное слагаемое  определено как:
Модификации этого алгоритма приведена в [W.K Leung,W.L Lee,A.Wu,L.Ping,“ Efficient implementation technique of LDPC decoder ”Electron.Lett..,vol.37(20),pp.1231-1232,Sept2001]. Данный метод не требует таблицы, но приводит к некоторому ухудшению характеристик, но зато позволяет сократить число операций при декодировании.
В настоящее время широкую известность получил класс “турбо-образных” (“turbo-like”) кодов, среди которых выделяются коды с “повторением – накоплением”, известные из [H. Jin, A. Khandekar and R. J. McEliece, “Irregular repeat-accumulate codes," Proceedings of the Second International Symposium on Turbo Codes and Related Topics, pp. 1-8, Brest, France, September 2000]. Кодирование кодов с “повторением – накоплением” осуществляют в следующем порядке: повторение каждого информационного символа, перемежение повторенных символов, накопление суммы по модулю 2 перемеженных символов. Данные коды обладают свойствами, как турбо-кодов, так и кодов с низкой плотностью проверок на четность и могут быть декодированы как в параллельном режиме – алгоритм обмена сообщениями, так и в последовательном режиме – алгоритм MAP. Следует отметить, что в последнем случае алгоритм по существу является гибридным, состоящим из MAP алгоритма декодирования сверточного кода с двумя состояниями и алгоритма обмена сообщениями с неравномерно повторенными информационными символами [J. Li, Low-Complexity, Capacity-Approaching Coding Schemes: Design, Analysis and Applications, Ph.D. dissertation, Texas A&M University, 2002. ]. Из [H. Jin, A. Khandekar and R. J. McEliece, “Irregular repeat-accumulate codes," Proceedings of the Second International Symposium on Turbo Codes and Related Topics, pp. 1-8, Brest, France, September 2000] известно, что наибольшая эффективность от применения достигается неравномерным или иррегулярным повторением информационных символов. Кроме того, характеристики кодов повторения с накоплением в большой степени характеризуются перемежителем, который совместно с шаблоном иррегулярного повторения и шаблоном накопления контрольных сумм определяют граф Таннера для данного кода. Требования к перемежителю заключаются в том, чтобы обеспечить достаточное разнесение повторенных символов, обеспечив тем самым отсутствие или малое число кодовых слов с низким весом. Закон перемежения или перестановку задают последовательностью неповторяющихся чисел, каждое из которых задействовано ровно один раз, таких, что они могут образовать натуральный ряд чисел (каждое последующее число на единицу больше предыдущего), если их расположить по возрастанию. Числа в виде натурального ряда это последовательность до перемежения, эти же числа в виде псевдослучайной последовательности это последовательность после перемежения.
Пример подобного кода приведен на фиг. 8. Это систематический код, состоящий из 7 переменных узлов, из которых 4 информационные, и 3 проверочных узла. Такому коду соответствует проверочная матрица вида:
Шаблон иррегулярных повторений представляет собой соответствие между количеством символов и числом их повторений. Для кода с фиг. 8 два информационных повторены один раз, один информационный символ повторен два раза, один информационный символ повторен три раза. Компактно шаблон повторений может быть записан в виде двух массивов: , где первый массив отражает количество повторений, а второй число повторенных символов. Рассмотрим процедуру кодирования. Пусть информационные символы будут  и индекс соответствует номеру переменного узла. Тогда после повторения последовательность символов примет вид . Общее число пвторенных символов семь. После перемежения по закону  имеем последовательность вида . Добиваясь того чтобы контрольная сумма на узле 3 была нулевой, формируем кодовый символ . Далее следуя "зигзаг" паттерну добиваемся равенству нулю остальных контрольных сумм: , .
Шаблон накопления контрольных сумм, аналогично шаблону повторения кодовых символов может быть записан в виде двух массивов , где первый массив отражает количество накоплений путем суммирования по модулю 2, а второй число накопленных символов.
При кодировании перемежение выполняется только среди повторенных информационных символов, а при декодировании к ним добавляют избыточные кодовые символы, полученные согласно паттерну "зигзаг". Говоря о перемежителе, обычно имеется ввиду перемежитель только информационных символов, так как только он несет псевдослучайную составляющую. Актуальной является задача построения частично параллельного перемежителя, в котором за один такт работы перемежают сразу  символов, где  - коэффициент параллельности перемежителя. Чем он больше, тем больше пропускная способность устройства. Для того чтобы схема параллельного перемежения была реализуемой, работа каждого из процессоров не должна приводить к конфликтам при доступе к памяти. К числу таких конфликтов можно, например, отнести попытку одновременной записи и чтения отдельной ячейки памяти. Память обычно реализуют в виде блоков (“банков”) памяти, таким образом, что к каждому блоку за один квант времени возможен либо доступ на запись (по указанному адресу), либо доступ на чтение.
В основе способа классический иррегулярный код повторений с накоплениями с низкой плотностью проверок на четность [D. Divsalar, H. Jin, and R. J. McEliece. "Coding theorems for ‘turbo-like’ codes." Proc. 36th Allerton Conf. on Communication, Control and Computing, Allerton, Illinois, Sept. 1998, pp. 201–210.], где применен новый эффективный перемежитель, и производят оценку качества декодирования, то есть выносится решение о правильности приема
Недостатком классической схемы при декодировании по алгоритму "распространение сообщений" является то, что затруднено согласование скоростей посредством перфорирования или выкалывания. При замене выколотого символа нулем и приходе этого нуля на проверочный узел декодирования в качестве исходящего сообщения будут выданы все нули, что снижает эффективность декодирования.
Наиболее близким аналогом по технической сущности к предлагаемому является устройство по патенту РФ 2323520, H03M 13/00 "Способ передачи голосовых данных в системе цифровой радиосвязи", принятое за прототип.
На фиг. 3 представлена схема передающего устройства (передающей стороны) устройства-прототипа, где обозначено:
1 – блок повторения информационных символов;
2 – блок перемежения информационных символов;
3 – блок разделения проверочных символов на группы;
4 – блок управления;
5 – блок суммирования;
6 – мультиплексор;
8 – блок памяти;
9 – канал связи;
24 – ключ.
Устройство-прототип состоит из передающего и приемного устройств, соединенных посредством канала связи 9, обеспечивающего передачу данных. Передающее устройство содержит последовательно соединенные блок повторения информационных символов 1, блок перемежения информационных символов 2, блок разделения проверочных символов на группы 3, блок суммирования 5, ключ 24, блок памяти 8 и мультиплексор 6, выход которого соединен с каналом связи 9, с выхода которого сигнал поступает на приемное устройство. Кроме того, выходы блока управления 4 подсоединены к управляющим входам блоков 1, 2, 3, 5, 6, и 24 соответственно. При этом первый вход блока повторения информационных символов 1 является первым входом передающего устройства, на который поступают пакеты данных, этот же вход соединен со вторым входом мультиплексора 6. Вход блока управления 4 является входом синхронизации, а также вторым входом передающего устройства.
На фиг. 4 представлена схема приемного устройства, где обозначено:
10 – блок формирования корреляционных откликов и оценки шумового параметра;
11 – блок разделения мягких решений;
12 – блок повторения проверочных символов;
13 – блок повторения информационных символов;
14 – блок перемежения информационных символов;
15 – блок формирования перемеженных мягких решений;
16 – итеративный декодер;
17 – блок вычисления контрольных сумм в декодированном кодовом слове;
18 – блок контроля ошибок в декодированном кодовом слове.
Приемное устройство содержит последовательно соединенные блок формирования корреляционных откликов и оценки шумового параметра 10, блок разделения мягких решений 11, блок повторения информационных символов 13, блок перемежения информационных символов 14, блок формирования перемеженных мягких решений 15, итеративный декодер 16, блок вычисления контрольных сумм в декодированном кодовом слове 17 и блок контроля ошибок в декодированном кодовом слове 18, первый выход которого является выходом устройства, а второй выход соединен со вторым входом итеративного декодера 16. Кроме того, другой выход блока разделения мягких решений 11 через блок повторения проверочных символов 12 соединен со вторым входом блока формирования перемеженных мягких решений 15, третий вход которого подключен ко второму выходу блока формирования корреляционных откликов и оценки шумового параметра 10, вход которого является входом приемного устройства, на который поступает сигнал с передающего устройства через канал связи 9.
Устройство-прототип работает следующим образом.
На передающей стороне сформированные пакеты данных, каждый из которых содержит упорядоченную последовательность информационных символов, поступают вход блока повторения информационных символов 1 и одновременно на второй вход мультиплексора 6. В блоке повторения информационных символов 1 каждый информационный символ повторяют определенное число раз, в зависимости от его номера по порядку в последовательности символов, формируя последовательность повторенных информационных символов, причем количество повторений определяется заранее. Последовательность повторенных информационных символов с выхода блока повторения информационных символов 1 поступает на вход блока перемежения информационных символов 2, где осуществляют перемежение в последовательности повторенных информационных символов, добиваясь достаточного разнесения идущих подряд повторенных информационных символов, и формируя последовательность перемеженных повторенных информационных символов. В блоке разделения проверочных символов на группы 3 разбивают перемеженные повторенные информационные символы на группы, затем в блоке суммирования 5 получают первый проверочный символ путем суммирования по заданному модулю начального значения переменной суммирования со всеми перемеженными повторенными информационными символами из первой группы, а проверочный символ  путем суммирования по заданному модулю проверочного символа  со всеми перемеженными повторенными информационными символами из группы . Полученные проверочные символы запоминают в блоке памяти 8. Запомненные проверочные символы поступают в мультиплексор 6, где формируют кодовое слово путем добавления проверочных символов к информационным символам. Через канал связи 9 сформированное кодовое слово передают на приемное устройство.
На приемной стороне сформированное в передающем устройстве кодовое слово поступает на вход блока формирования корреляционных откликов и оценки шумового параметра 10, где формируют принятые корреляционные отклики на каждый из переданных кодовых символов и выполняют оценку шумового параметра смеси сигнал плюс шум, которая приближенно равна величине стандартного отклонения эквивалентного гауссовского белого шума, которым аппроксимируются помехи в канале, а затем формируют мягкие решения о принятых кодовых символах, используя полученную оценку шумового параметра смеси сигнал плюс шум. Полученные мягкие решения поступают на вход блока разделения мягких решений 11, где происходит разделение мягких решений о принятых кодовых символах на решения об информационных символах и решения о проверочных символах. Мягкие решения об информационных символах с блока разделения мягких решений 11 поступают на вход блока повторения информационных символов 13, где повторяют мягкие решения об информационных символах в соответствии с шаблоном повторения информационных символов. Мягкие решения о проверочных символах с блока разделения мягких решений 11 поступают на вход блока повторения проверочных символов 12, где повторяют мягкие решения о проверочных символах, по крайней мере, два раза за исключением последнего проверочного символа. Для мягких решений об информационных символах выполняют перемежение аналогичное перемежению на передающей стороне в блоке перемежения информационных символов 14. Затем в блоке формирования перемеженных мягких решений 15 формируют группы перемеженных мягких решений об информационных символах аналогичные группам соответствующих информационных символов на передающей стороне, используя сигналы с блока проверочных символов 12 и с блока формирования корреляционных откликов и оценки шумового параметра 10, причем первую группу перемеженных мягких решений дополняют мягким решением, соответствующим начальному значению переменной суммирования, и первой копией мягкого решения о первом проверочном символе, образуя первое кодовое слово кода обобщенной проверки на четность, n-ю группу перемеженных мягких решений дополняют второй копией n-го проверочного символа и первой копией мягкого решения об n-м проверочном символе, образуя n-е кодовое слово кода обобщенной проверки на четность. Сформированные перемеженные мягкие решения поступают на первый вход итеративного декодера 16, в котором формируется декодированное кодовое слово. Каждое декодированное кодовое слово в блоке вычисления контрольных сумм в декодированном кодовом слове 17 умножают на проверочную матрицу, получая упорядоченную последовательность контрольных сумм, если все контрольные суммы равны нулю, то кодовое слово считают декодированным верно, если количество контрольных сумм отличных от нуля нечетно и последняя контрольная сумма отлична от нуля, то заменяют ее нулем, если количество контрольных сумм отличных от нуля нечетно и последняя в последовательности контрольная сумма равна нулю, то ее заменяют любым отличным от нуля значением, разбивают последовательность контрольных сумм на пары, в которые входят элементы последовательности, идущие подряд, причем каждая контрольная сумма входит только в единственную пару, в каждой паре вычисляют разность номеров контрольных сумм, складывают все полученные разности номеров контрольных сумм. Затем в блоке контроля ошибок в декодированном кодовом слове 18 сравнивают полученное число с заданным порогом, если число превышает установленный порог, то информационную часть кодового слова считают декодированной неверно, если полученное число меньше заданного порога, то информационную часть кодового слова считают декодированной верно.
Задача предлагаемого технического решения – разработка приемо-передающего устройства, которое позволяет увеличить энергетический выигрыш помехоустойчивого кодирования за счет применения алгоритма гибридного запроса-повторения.
Для решения поставленной задачи в устройство передачи данных на основе кодов с низкой плотностью проверок на четность, состоящее из передающего и приемного устройств, соединенных посредством канала связи, обеспечивающего передачу данных, при этом передающее устройство содержит последовательно соединенные блок повторения информационных символов, блок перемежения информационных символов, блок разделения проверочных символов на группы, блок суммирования, а также последовательно соединенные блок памяти и мультиплексор, выход которого соединен с каналом связи, кроме того, выходы блока управления подсоединены к управляющим входам блока повторения информационных символов, блока перемежения информационных символов, блока разделения проверочных символов на группы, блока суммирования и мультиплексора соответственно; вход блока повторения информационных символов является первым входом передающего устройства, на который поступают пакеты данных, этот же вход соединен со вторым входом мультиплексора; вход блока управления является входом сигналов синхронизации, а также вторым входом передающего устройства; приемное устройство содержит последовательно соединенные блок формирования корреляционных откликов и оценки шумового параметра, блок разделения мягких решений, блок повторения информационных символов, блок перемежения информационных символов, блок формирования перемеженных мягких решений, первый итеративный декодер, первый блок вычисления контрольных сумм в декодированном кодовом слове, первый блок контроля ошибок в декодированном кодовом слове, первый выход которого является первым выходом устройства, а второй выход соединен со вторым входом первого итеративного декодера, кроме того, второй выход блока разделения мягких решений через блок повторения проверочных символов подключен ко второму входу блока формирования перемеженных мягких решений, третий вход которого подсоединен ко второму выходу блока формирования корреляционных откликов и оценки шумового параметра, вход которого является входом приемного устройства, согласно изобретению, введены канал обратной связи, в передающее устройство – блок межпакетного суммирования, управляющий вход которого подключен к соответствующему выходу блока управления, первый и второй входы блока межпакетного суммирования подсоединены к соответствующим выходам блока памяти, выход блока межпакетного суммирования подключен к третьему входу мультиплексора; выход блока суммирования соединен с входом блока памяти, управляющий вход которого подсоединен к соответствующему выходу блока управления, второй вход блока управления, который является входом сигнала обратной связи с приемного устройства, переданного через выход канала обратной связи и третьим входом передающего устройства; в приемное устройство – блок хранения и модификации мягких решений, первый выход-вход которого через последовательно соединенные второй итеративный декодер, второй блок вычисления контрольных сумм в декодированном кодовом слове и второй блок контроля ошибок в декодированном кодовом слове, соединен с одним входом канала обратной связи, второй выход второго блока контроля ошибок в декодированном кодовом слове соединен со вторым входом второго итеративного декодера, а третий выход второго блока контроля ошибок в декодированном кодовом слове является вторым выходом приемного устройства, при этом выход блока формирования перемеженных мягких решений соединен с входом блока хранения и модификации мягких решений, второй выход-вход которого соединен с входом-выходом первого итеративного декодера; третий выход первого блока контроля ошибок в декодированном кодовом слове соединен с другим входом канала обратной связи.
Отличительными (новыми) признаками заявляемого устройства передачи данных относительно прототипа являются следующие:
- канал обратной связи, по которому передают сигналы обратной связи для передающего устройства от первого и второго блока контроля ошибок в декодированном слове, если информационная часть кодового слова декодирована неверно, то формируют сигнал запроса повторной передачи по каналу обратной связи для передающей стороны;
- в передающем устройстве: блок межпакетного суммирования, где на передающей стороне при получении сигнала запроса повторной передачи формируют пакет с кодово-сопряженной частью, для чего в очередном кодированном пакете часть кодовых символов заменяют суммой по модуля два с кодовыми символами ранее переданного и ошибочно декодированого пакета, формируя тем самым кодово-сопряженную часть;
- в приемном устройстве:
блок хранения и модификации мягких решений, где модифицируют мягкие решения в кодово-сопряженной части в тех позициях, в которых заменяли кодовые символы суммой символов разных пакетов для чего заменяют знак на противоположный у принятого мягкого решения, если восстановленный кодовый символ текущего пакета соответствует логической единице, получая модифицированную последовательность мягких решений для ошибочного пакета;
- второй итеративный декодер, где повторно декодируют ошибочный пакет, используя модифицированную последовательность мягких решений для ошибочного пакета как дополнительную информацию в тех позициях, в которых заменяли кодовые символы суммой символов разных пакетов, передают по каналу обратной связи сигналы, характеризующие результативность декодирования кодово-сопряженных пакетов;
- второй блок вычисления контрольных сумм в декодированном кодовом слове, где каждое декодированное кодовое слово умножают на проверочную матрицу, получая упорядоченную последовательность контрольных сумм, если все контрольные суммы равны нулю, то кодовое слово считают декодированным верно, если количество контрольных сумм отличных от нуля нечетно и последняя контрольная сумма отлична от нуля, то заменяют ее нулем, если количество контрольных сумм отличных от нуля нечетно и последняя в последовательности контрольная сумма равна нулю, то ее заменяют любым отличным от нуля значением;
- второй блок контроля ошибок в декодированном кодовом слове, где разбивают последовательность контрольных сумм на пары, в которые входят элементы последовательности, идущие подряд, причем каждая контрольная сумма входит только в единственную пару, в каждой паре вычисляют разность номеров контрольных сумм, складывают все полученные разности номеров контрольных сумм, сравнивают полученное число с заданным порогом, если число превышает установленный порог, то информационную часть кодового слова считают декодированной неверно, если полученное число меньше заданного порога, то информационную часть кодового слова считают декодированной верно.
Графические материалы, используемые в описании:
фиг. 1 – алгоритм декодирования на графе: обмен сообщениями;
фиг. 2 – граф Петерсона и заданный на нем код по способу Таннера;
фиг. 3 – схема передающего устройства-прототипа;
фиг. 4 – схема приемного устройства-прототипа;
фиг. 5 – схема передающей стороны предлагаемого устройства;
фиг. 6 – схема приемной стороны предлагаемого устройства;
фиг. 7 – способ обнаружения ошибок без CRC;
фиг. 8 – пример кода перемежений с накоплениями;
фиг. 9 – результаты моделирования: зависимость битовой ошибки от отношения сигнал-шум для  и .
Заявляемое устройство содержит: передающее устройство (передающая сторона), схема которого представлена на фиг. 5, приемное устройство (приемная сторона) и канал обратной связи – на фиг. 6.
На фиг. 5 введены следующие обозначения:
1 – блок повторения информационных символов;
2 – блок перемежения информационных символов;
3 – блок разделения проверочных символов на группы;
4 – блок управления;
5 – блок суммирования;
6 – мультиплексор;
7 – блок межпакетного суммирования;
8 – блок памяти;
9 – канал связи.
Передающее устройство, представленное на фиг. 5, содержит последовательно соединенные блок повторения информационных символов 1, блок перемежения информационных символов 2, блок разделения проверочных символов на группы 3, блок суммирования 5, блок памяти 8, блок межпакетного суммирования 7 и мультиплексор 6, выход которого соединен с каналом связи 9. Кроме того, выходы блока управления 4 соединены с управляющими входами блоков 1, 2, 3, 5, 6, 7, 8 соответственно.
Второй выход блока памяти 8 соединен с третьими входами блока межпакетного суммирования 7 и мультиплексора 6.
Первый вход блока повторения информационных символов 1 является первым входом передающего устройства, на который поступают пакеты данных, этот же вход соединен с первым входом мультиплексора 6. Первый вход блока управления 4 является входом сигнала обратной связи на автоматический запрос повторение, он же является вторым входом передающего устройства.
Сигналы с выходов блока управления 4 являются управляющими сигналами, которые, в том числе, обеспечивают синхронизацию остальных блоков.
Через канал связи 9 сигнал подается на приемное устройство.
На фиг. 6 обозначено:
10 – блок формирования корреляционных откликов и оценки шумового параметра;
11 – блок разделения мягких решений;
12 – блок повторения проверочных символов;
13 – блок повторения информационных символов;
14 – блок перемежения информационных символов;
15 – блок формирования перемеженных мягких решений;
16, 20 – первый и второй итеративные декодеры;
17, 21 – первый и второй блоки вычисления контрольных сумм в декодированном кодовом слове;
18, 22 – первый и второй блоки контроля ошибок в декодированном кодовом слове;
19 – блок хранения и модификации мягких решений;
23 – канала обратной связи
Приемное устройство, представленное на фиг. 4, содержит последовательно соединенные блок формирования корреляционных откликов и оценки шумового параметра 10, блок разделения мягких решений 11, блок повторения проверочных символов 12, блок формирования перемеженных мягких решений 15, первый итеративный декодер 16, первый блок вычисления контрольных сумм в декодированном кодовом слове 17, первый блок контроля ошибок в декодированном кодовом слове 18, выход которого является первым выходом приемного устройства. Выход блока разделения мягких решений 11 через последовательно соединенные блок повторения информационных символов 13 и блок перемежения информационных символов 14 соединен со вторым входом блока формирования перемеженных мягких решений 15, выход которого соединен с входом блока хранения и модификации мягких решений 19, первый вход-выход которого через последовательно соединенные второй итеративный декодер 20, второй блок вычисления контрольных сумм в декодированном кодовом слове 21 и второй блок контроля ошибок в декодированном кодовом слове 22 соединен с входом канала обратной связи 23. При этом второй выход блока контроля ошибок в декодированном кодовом слове 22 соединен со вторым входом второго итеративного декодера 20. Второй вход-выход блока хранения и модификации мягких решений 19 соединен с входом-выходом первого итеративного декодера 16, второй вход которого подсоединен к третьему выходу блока контроля ошибок в декодированном кодовом слове 18, второй выход которого соединен со вторым входом канала обратной связи 23. Второй выход блока формирования корреляционных откликов и оценки шумового параметра 10 соединен с третьим входом блока формирования перемеженных мягких решений 15.
Входом приемного устройства является вход блока формирования корреляционных откликов и оценки шумового параметра 10, на который поступает сигнал с передающего устройства через канал связи 9. Второй выход блока контроля ошибок в декодированном кодовом слове 22 является вторым выходом приемного устройства.
Первый 16 и второй 20 итеративные декодеры идентичны и выполнены по аналогичной схеме итеративного декодера устройства-прототипа с единственным отличием: добавлен вход-выход позволяющий сохранять восстановленные мягкие решения в блоке хранения и модификации мягких решений 19 (фиг. 6), использовать модифицированные мягкие решения из блока хранения и модификации мягких решений 19 (фиг. 6) как априорную информацию, суммируя ее с восстановленными мягкими решениями на данной итерации.
Работает устройство следующим образом.
На передающей стороне сформированные пакеты данных, каждый из которых содержит упорядоченную последовательность информационных символов, поступают вход блока повторения информационных символов 1 и одновременно на первый вход мультиплексора 6. В блоке повторения информационных символов 1 каждый информационный символ повторяют определенное число раз, в зависимости от его номера по порядку в последовательности символов, формируя последовательность повторенных информационных символов, причем, количество повторений определяется заранее. Последовательность повторенных информационных символов с выхода блока повторения информационных символов 1 поступает на вход блока перемежения информационных символов 2, где осуществляют перемежение в последовательности повторенных информационных символов, добиваясь достаточного разнесения идущих подряд повторенных информационных символов и формируя последовательность перемеженных повторенных информационных символов. В блоке разделения проверочных символов на группы 3 разбивают перемеженные повторенные информационные символы на группы, затем в блоке суммирования 5 получают первый проверочный символ путем суммирования по заданному модулю начального значения переменной суммирования со всеми перемеженными повторенными информационными символами из первой группы, а проверочный символ  путем суммирования по заданному модулю проверочного символа  со всеми перемеженными повторенными информационными символами из группы . Полученные проверочные символы запоминают в блоке памяти 8. Запомненные проверочные символы поступают в мультиплексор 6, где формируют кодовое слово путем добавления проверочных символов к информационным символам. Через канал связи 9 сформированное кодовое слово передают на приемное устройство. В случае получения по каналу обратной связи сигнала запроса на повторную передачу формируют пакет с кодово-сопряженной частью, для чего в блоке межпакетного суммирования 7 суммируют кодовые символы текущего пакета с кодовыми символами ошибочно декодированного пакета, сохраненного в блоке памяти 8. В мультиплексоре 6 мультиплексируют кодово-сопряженную часть пакета, полученную с блока межпакетного суммирования 7 и кодовые символы текущего пакета, которые также сохраняют в блоке памяти 8.
На приемной стороне сформированное в передатчике кодовое слово поступает на вход блока формирования корреляционных откликов и оценки шумового параметра 10, где формируют принятые корреляционные отклики на каждый из переданных кодовых символов и выполняют оценку шумового параметра смеси сигнал плюс шум, которая приближенно равна величине стандартного отклонения эквивалентного гауссовского белого шума, которым аппроксимируются помехи в канале, а затем формируют мягкие решения о принятых кодовых символах, используя полученную оценку шумового параметра смеси сигнал плюс шум. Полученные мягкие решения поступают на вход блока разделения мягких решений 11, где происходит разделение мягких решений о принятых кодовых символах на решения об информационных символах и решения о проверочных символах. Мягкие решения об информационных символах с блока разделения мягких решений 11 поступают на вход блока повторения информационных символов 13, где повторяют мягкие решения об информационных символах в соответствии с шаблоном повторения информационных символов. Мягкие решения о проверочных символах с блока разделения мягких решений 11 поступают на вход блока повторения проверочных символов 12, где повторяют мягкие решения о проверочных символах, по крайней мере, два раза за исключением последнего проверочного символа. Для мягких решений об информационных символах выполняют перемежение, аналогичное перемежению на передающей стороне в блоке перемежения информационных символов 14. Затем в блоке формирования перемеженных мягких решений 15 формируют группы перемеженных мягких решений об информационных символах, аналогичные группам соответствующих информационных символов на передающей стороне, используя сигналы с блока проверочных символов 12 и с блока формирования корреляционных откликов и оценки шумового параметра 10, причем первую группу перемеженных мягких решений дополняют мягким решением, соответствующим начальному значению переменной суммирования, и первой копией мягкого решения о первом проверочном символе, образуя первое кодовое слово кода обобщенной проверки на четность, n-ю группу перемеженных мягких решений дополняют второй копией n-го проверочного символа и первой копией мягкого решения об n-м проверочном символе, образуя n-е кодовое слово кода обобщенной проверки на четность. Сформированные перемеженные мягкие решения поступают на первый вход первого итеративного декодера 16 (на первый коммутатор 30 фиг. 5), в котором итеративно повторяют процесс обмена исходящими и входящими сообщениями таким образом, что исходящее сообщение кодового слова обобщенного кода повторений является входящим сообщением кодового слова кода обобщенной проверки на четность, а исходящее сообщение кода обобщенной проверки на четность является входящим сообщением кодового слова обобщенного кода повторений формируя на каждой итерации последовательность восстановленных мягких решений, а из последовательности восстановленных мягких решений формируют декодированные кодовые слова.
Каждое декодированное кодовое слово в блоке вычисления контрольных сумм в декодированном кодовом слове 17 умножают на проверочную матрицу, получая упорядоченную последовательность контрольных сумм, если все контрольные суммы равны нулю, то кодовое слово считают декодированным верно, если количество контрольных сумм отличных от нуля нечетно и последняя контрольная сумма отлична от нуля, то заменяют ее нулем, если количество контрольных сумм отличных от нуля нечетно и последняя в последовательности контрольная сумма равна нулю, то ее заменяют любым отличным от нуля значением, разбивают последовательность контрольных сумм на пары, в которые входят элементы последовательности, идущие подряд, причем каждая контрольная сумма входит только в единственную пару, в каждой паре вычисляют разность номеров контрольных сумм, складывают все полученные разности номеров контрольных сумм. Затем в первом блоке контроля ошибок в декодированном кодовом слове 18 сравнивают полученное число с заданным порогом, если число превышает установленный порог, то информационную часть кодового слова считают декодированной неверно, если полученное число меньше заданного порога, то информационную часть кодового слова считают декодированной верно.
Восстановленные проверочные символы пакета, в котором детектирована ошибка, сохраняют в блоке хранения и модификации мягких решений 19, где и изменяют знак мягкого решения на противоположный, если восстановленные мягкие решения в тех позициях, в которых заменяли кодовые символы суммой символов разных пакетов в кодово-сопряженной части пакета соответствуют логической единице, получая мягкие решения текущего пакета, которые используют как дополнительную информацию при декодировании текущего пакета первым итеративным декодером 16. Восстановленную последовательность мягких решений текущего пакета сохраняют в блоке хранения и модификации мягких решений 19, там же изменяют знак мягкого решения на противоположный, если восстановленные мягкие решения текущего пакета в тех позициях, в которых заменяли кодовые символы суммой символов разных пакетов в кодово-сопряженной части пакета соответствуют логической единице, получая модифицированную последовательность мягких решений для ошибочного пакета. Повторно декодируют ошибочный пакет вторым итеративным декодером 20, используя модифицированную последовательность мягких решений для ошибочного пакета, как дополнительную информацию в тех позициях, в которых заменяли кодовые символы суммой символов разных пакетов. Передают по каналу обратной связи 23 сигналы, характеризующие результативность декодирования кодово-сопряженных пакетов.
Алгоритм обнаружения ошибок в кодовом слове представлен на фиг. 7.
Обнаружение ошибок в заявляемом способе передачи данных в цифровой системе связи может быть пояснено следующим примером. Пусть мы имеем код “повторение с накоплением” заданный двудольным регулярным графом. Рассмотрим различные конфигурации ошибок. Отметим случай, когда существуют ошибочно декодированные переменные вершины, но все контрольные суммы равны нулю. Это случай необнаружимой ошибки. Рассмотрим также случай, когда ошибки только в проверочной части кодового слова. Заметим, что каждая ошибка в проверочной части вызывает неравенство нулю двух соседних контрольных сумм. Однако неравные нулю контрольные суммы при ошибке в информационной части разнесены на расстояние пропорциональное параметру разнесения интерливера (перемежителя). Таким образом, при наличии единственной ошибки легко определить к какому символу она относится: информационному или проверочному. Для этого достаточно рассмотреть разность номеров проверочных вершин, соответствующих неравным нулю контрольным суммам. Если таковая разность равна 1, то ошибочный символ однозначно можно отнести к проверочным символам, если больше, то ошибочный символ информационный.
Переходя к случаю многих ошибок, алгоритм состоит в следующем:
• если число отличных от нуля контрольных сумм нечетно, то изменяют контрольное значение последней суммы, добиваясь четного числа контрольных сумм;
• последовательно разбивают контрольные суммы на пары, вычисляют сумму разностей адресов проверочных вершин;
• сравнивают полученное значение с порогом, если оно меньше порога, то относят ошибки только к проверочным символам.
Таким образом, обнаружение ошибок осуществляют без CRC, тем самым повышая качество радиосвязи за счет снижения количества избыточных передаваемых кодовых символов, обеспечивая одновременно обнаружение и исправление ошибок.
Все блоки, входящие в систему связи могут быть реализованы на процессоре, ПЛИС, например, производства фирм Altera и Xilinx, а также на специализированной заказной микросхеме.
Таким образом, технический результат состоит в получении энергетического выигрыша кодирования в среднем 0.5 Дб, что подтверждается результатами моделирования, представленными на Фиг. 9, где указанный выигрыш получен при . На Фиг. 9 представлены результаты моделирования: зависимость битовой ошибки от отношения сигнал-шум для  для . Для сравнения, помимо прототипа и изобретения приведены результаты моделирования аналога данного изобретения по источнику [Halford, Thomas & Bayram, Metin & Kose, Cenk & M. Chugg, Keith & Polydoros, Andreas. (2008). The F-LDPC Family: High-Performance Flexible Modern Codes for Flexible Radio. 376 - 380. 10.1109/ISSSTA.2008.75.]. Моделирование устройства проводили со следующими параметрами: число информационных символов , шаблон повторения информационных символов  размер перемежителя , первые  символа перемежителя , а остальные получают как  , где , кодово-сопряженную часть составляет каждый 9-ый проверочный символ.