Адаптивное устройство кодирования/декодирования данных на основе кодов низкой плотности проверок на четность

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ АДАПТИВНОЕ УСТРОЙСТВО КОДИРОВАНИЯ/ДЕКОДИРОВАНИЯ ДАННЫХ НА ОСНОВЕ КОДОВ НИЗКОЙ ПЛОТНОСТИ ПРОВЕРОК НА ЧЕТНОСТЬ(71) Заявитель Учреждение образования Белорусский государственный технологический университет(72) Авторы Урбанович Павел Павлович Пацей Наталья Владимировна Романенко Дмитрий Михайлович Шиман Дмитрий Васильевич(73) Патентообладатель Учреждение образования Белорусский государственный технологический университет(57) Адаптивное устройство кодирования/декодирования данных на основе кодов низкой плотности проверок на четность, содержащее передатчик, приемник данных и беспроводной канал передачи, вход которого соединен с выходом передатчика данных, а выход соединен со входом приемника данных, при этом передатчик состоит из источника данных,кодера на основе кода с низкой плотностью проверок на четность и модулятора, выход которого является выходом передатчика данных, а вход соединен с выходом кодера, а приемник данных состоит из демодулятора и декодера кодов низкой плотности проверок на четность, выход которого соединен с выходом приемника данных, а вход - с выходом демодулятора, вход которого соединен со входом приемника данных, отличающееся тем, Фиг. 1 82962012.06.30 что в приемник данных добавлены демодулятор, вход которого является вторым выходом беспроводного канала связи, а выход - вторым входом кодера низкой плотности проверок на четность, и блок контроля четности, вход которого является выходом кодера, а выход соответственно - входом модулятора, а в передатчик добавлены модулятор, блок анализа и блок контроля четности, вход которого является выходом демодулятора, а выход - первым входом блока анализа, при этом второй вход блока анализа является выходом демодулятора, а выход - вторым входом декодера кода низкой плотности проверок на четность и входом модулятора, выход которого является вторым выходом приемника данных и вторым входом беспроводного канала.(56) 1..,.,.5170/. -// -25.06.2008. 2., . -, , 1963. 90 . 3. Патент 2341894 2, МПК 03 13/1104 1/00, 2008. 4. Патент 0199068, МПК 03 13/0506 11/10, 2009. 5.,.,.,, . .//,. . - 2004. . 50. - . 12. - .2966-2984. 6. Пацей Н.В. Моделирование переменных кодов низкой плотности проверок на четность. Труды БГТУ. Сер. . Физ.-мат. науки и информатика. Вып. . - Минск. БГТУ,2011. - С. 132-135. Полезная модель к устройству кодирования и декодирования блочных кодов низкой плотности проверки на четность (НППЧ) (- ), обладающему переменной длиной кодового слова, переменной скоростью кодирования и плотностью проверочной матрицы, которое может быть использовано в системах беспроводной связи для повышения скорости и надежности передачи. Надежная передача информации обеспечивается использованием канальных схем обнаружения и коррекции ошибок. Коды низкой плотности проверок на четность были предложены 1, 2 для использования в спутниковых и беспроводных телекоммуникационных системах связи, волоконно-оптических и системах хранения информации. Они относятся к линейным блочным кодам и задаются параметрами (, , , ), где- длина кодового блока,- длина информационного блока,- количество единиц в каждом столбце (или функция распределения, если количество единиц меняется),- количество единиц в каждой строке (или функция распределения, если количество единиц меняется). Коды НППЧ описываются с помощью проверочной матрицыразмера (-). Каждой проверочной матрицеставится в соответствие порождающая матрица . При кодировании НППЧ-кодами чаще вместо порождающей матрицы используют проверочную 2. Известен устройство и способ кодирования/декодирования данных на основе кода разряженного контроля четности с переменной длиной блока и скоростью кодирования 3. Согласно 3 устройство содержит четыре типа матриц контроля четности, что позволяет использовать четыре скорости кодирования 1/2, 2/3, 3/4 и 5/6 и изменять длину кодового блока в пределах 96, 192, 288, 384, 480, 576, 672, 768, 864 и 960. Недостатком устройства является ограничение на диапазон скоростей и необходимость генерации проверочных матриц в процессе работы устройства. Указанные недостатки ограничивают количество 2 82962012.06.30 возможных кодов, используемых в устройстве, а также требуют дополнительного времени на генерацию проверочных матриц. Наиболее близким техническим решением к предлагаемому устройству является устройство кодирования/декодирования данных для кодов низкой плотности проверок на четность в беспроводных коммуникационных системах, содержащее передатчик, приемник данных и беспроводной канал передачи, вход которого соединен с выходом передатчика данных, а выход соединен со входом приемника данных, при этом передатчик состоит из источника данных, кодера на основе кода с низкой плотностью проверок на четность и модулятора, выход которого является выходом передатчика данных, а вход соединен с выходом кодера, а приемник данных состоит из демодулятора и декодера кодов низкой плотности проверок на четность, выход которого соединен с выходом приемника данных, а вход - с выходом демодулятора, вход которого соединен со входом приемника данных 4. Устройство обеспечивает формирование проверочной матрицы кода на основе генерации базовой матрицы размером 9696 и 96 перестановочных матриц, расстановку перестановочных матриц в проверочной, что в итоге обеспечивает результирующие скорости кода 1/2, 2/3, 3/4 и дает возможность изменять длину информационного блока в пределах 36, 42, 48, 54, 56, 60, 63, 64, 66, 72, 78, 80, 81, 84, 88, 90, 96, 99, 102, 104, 108, 112, 114,117, 120, 128, 132, 135, 136, 138, 144, 152, 153, 160, 162, 168, 171, 176, 180, 184, 189, 192,198, 207, 216. Недостатками представленного в 4 устройства является ограничение на скорость кодирования, короткая длина информационного блока и невозможность изменения параметров НППЧ-кода в процессе передачи без отключения канала. Задачей настоящей полезной модели является повышение эффективности функционирования устройства кодирования/декодирования данных путем изменения динамического изменения параметров кода скорости, величины веса столбцов проверочной матрицы(плотности проверочной матрицы) и длины кодового слова, в зависимости от изменяемого во времени значения оценки качества канала передачи, что позволит увеличить производительность системы передачи информации и увеличить ее надежность. Поставленная задача решается тем, что в устройство кодирования/декодирования данных на основе кодов низкой плотности проверок на четность, содержащее передатчик,приемник данных и беспроводной канал передачи, вход которого соединен с выходом передатчика данных, а выход соединен со входом приемника данных, при этом передатчик состоит из источника данных, кодера на основе кода с низкой плотностью проверок на четность и модулятора, выход которого является выходом передатчика данных, а вход соединен с выходом кодера, а приемник данных состоит из демодулятора и декодера кодов низкой плотности проверок на четность, выход которого соединен с выходом приемника данных, а вход - с выходом демодулятора, вход которого соединен со входом приемника данных, введены в приемник данных - демодулятор, вход которого является вторым выходом беспроводного канала связи, а выход - вторым входом кодера низкой плотности проверок на четность, и блок контроля четности, вход которого является выходом кодера,а выход соответственно - входом модулятора, а в передатчик добавлены модулятор, блок анализа и блок контроля четности, вход которого является выходом демодулятора, а выход - первым входом блока анализа, при этом второй вход блока анализа является выходом демодулятора, а выход - вторым входом декодера кода низкой плотности проверок на четность и входом модулятора, выход которого является вторым выходом приемника данных и вторым входом беспроводного канала. Изобретение поясняется чертежами фиг. 1-5. Фиг. 1 - структурная схема адаптивного устройства кодирования/декодирования данных на основе кодов низкой плотности проверок на четность. Фиг. 2 - структурная схема блока НППЧ-кодера. 3 82962012.06.30 Фиг. 3 - структурная схема блока НППЧ-декодера. Фиг. 4 - направление изменения параметров кода по табл. 2 при непрерывном ухудшении оценки качества канала. Фиг. 5 - результаты экспериментального моделирования, зависимостьот . Для оптимизации системы передачи информации в предлагаемом техническом решении изменен, по сравнению с прототипом 4, способ формирования проверочной матрицы кодаи добавлена возможность динамического (в процессе передачи) изменения параметров НППЧ-кода путем контроля скорости кода, размера кодового слова и плотности проверочной матрицы . В результате устройство динамически адаптируется к качеству канала в соответствии с рассчитанной анализатором оценкой. Комбинация параметров , ,позволяет получить широкий спектр кодов. В дальнейшем НППЧ-код, построенный на основе общего алгоритма, но обеспечивающий различные кодовые скорости, размеры кодового слова и плотность проверочной матрицы, назовем переменным кодом низкой плотности проверок на четность (ПНППЧ). Обобщенная структурная схема адаптивного устройства кодирования/декодирования данных на основе переменных кодов с низкой плотностью проверок на четность (фиг. 1) состоит из передатчика 1, содержащего блок источника данных 2, выход 3 которого соединен с первым входом НППЧ-кодера 4, выход 5 которого является входом блока контроля четности 6, который добавляет к кодированной последовательности значение,вычисленное на основе -кода . Блок 6 добавлен для динамического мониторинга качества канала на стороне передатчика 1. Полученный кодовый блок с выхода 7 передается на первый вход блока модуляции/демодуляции 8, выход 9 которого является выходом приемника 1 и первым входом беспроводного канала связи 10. Первый выход 11 беспроводного канала связи 10 является входом приемника данных 12,содержащего блок модуляции/демодуляции 13, первым входом соединенный с первым выходом 11 канала связи, а первым выходом 14 - с первым информационным входом 15 НППЧ-декодера 16, первым выходом 14 - со входом 17 блока контроля четности 18 и первым выходом 14 - с первым входом 19 блока анализа 20. Блок контроля четности 18 приемника 12 аналогичен по функциональному назначению блоку 6 передатчика данных 1. Блоки 6 и 18 не могут локализировать битовые ошибки, так как существует ограничение на длину измеряемого блока (-4, -6, -16 или -32), кроме того, возможны ситуации компенсации ошибок. Тем не менее, в результате добавления блоков контроля четности не требуется отключения канала для определения его качества. Вычисленные блоком 18 значения поступают через выход 21 на второй вход блока анализа 20, который на основе расчетного и вычисленного значения вычисляет и принимает решение о качестве канала.- коэффициент ошибок по блокам, который равен отношению числа ошибочных блоков данных (рассчитывается на основе переданной величиныи рассчитанной блоком контроля четности 18) к общему числу переданных блоков. Ошибочным считается блок, содержащий хотя бы один ошибочный бит. В случае длительного анализа система передачи будет медленно адаптируемая, поэтому в данном техническом решении период измерения будет зависеть от числа переданных бит. Анализатор выполняет деление качества канала на шесть категорий и от 10 до 14 подкатегорий в каждой категории на основании . Категории/подкатегории качества канала представлены в табл. 1. В зависимости от категории/подкатегории и текущих параметров кода (, , , ) блок анализа 20 выполняет переключение ПНППЧ-кода в соответствии с перечнем предопределенных НППЧ-кодов, предусмотренных данным решением и представленных в табл. 2. Блок анализа 20 формирует выход 22, поступающий на второй вход модулятора/демодулятора 13 и через второй выход 23 блока 13, являющийся выходом приемника 12 и вторым входом беспроводного канала связи 10. Второй выход беспроводного канала связи 10 является входом передатчика 1 и вторым входом 24 блока модуляции/демодуляции 8, вто 4 82962012.06.30 рой выход которого соединен со вторым входом 25 НППЧ-кодера 4. Выход 22 блока анализа 20 является вторым входом НППЧ-декодера 16. Таким образом, выход 22 управляет параметрами кода в НППЧ-кодере 4 и НППЧ-декодере 16. Декодированная последовательность НППЧ-декодера 16 поступает с выхода 26 и является вторым выходом приемника 12. В описанной схеме устройства (фиг. 1) сигналы питания и синхронизации не показаны. Таблица 1 Категории/подкатегории качества канала Категория /подкатегория Значение(высокое)0(хорошее) 10-910-7 1 - 14(среднее) 10-710-5 1-14(ниже среднего) 10-510-4 1 - 12(низкое) 10-410-3 1 - 10(деградация)10-3 Длины блоков кодового словавыбраны в соответствии с - .821, .826 и.2100 рекомендациями, а значениев таблице соответствует количеству единиц в столбцах проверочной матрицы. На фиг. 2 представлена структурная схема НППЧ-кодера 4, содержащая блок кодирования 27 и оперативное запоминающее устройство (ЗУ) 28. Оперативное запоминающее устройство 28 предназначено для хранения различных конфигураций 54 альтернативных проверочных матриц по табл. 2. По второму входу 25, поступающему с блока анализа 20 приемника 12 через беспроводной канал связи 10 и блок модуляции/демодуляции 8, подается адрес ячеек памяти, из которых должна быть считана проверочная матрица (сигналы записи/считывания на фиг. 2 не указаны) и передана через первый выход 29 и второй выход 30 ЗУ 28 на второй и третий входы блока кодирования 27 соответственно. 5 82962012.06.30 Проверочная матрица регулярного НППЧ-кодаразделена на две подматрицы(1),где- двойная диагональная матрица размера (-)(-), содержит проверочную часть(соответствует избыточным символам кодового слова) и- матрица размера (-), содержит информационную часть (соответствует информационным символам кодового слова). Так как проверочная матрица НППЧ-кодаявляется разряженной (содержит малое количество единиц) и структура матрицыпостоянна, то хранение матрицыв ЗУ 28 может быть организовано через два массива размером , где- общее количество единиц вматрице,. Условно назовем эти массивы строка и конец строки. В массиве строка хранятся позиции (индексация начинается с нуля) последовательных строк, где размещены единицы. В случае перехода единицы из текущей на следующую строку в исходной матрице(т.е. последняя единица в строке) в массиве конец строки выставляется флаг 1, в противном случае - 0. Например, для матрицыразмера 55 с количеством единиц 10 массивы будут выглядеть следующим образом Индекс 0 1 2 3 4 5 6 Массивстрока 0 1 2 3 4 0 5 Массивконец строки 1 1 1 1 1 0 1. При выборе матрицы на первый выход 29 и второй выход 30 блока 28 поступают значения массивов конец строки и строка соответственно. Блок кодирования 27 функционально представляет собой умножитель матрицына информационный векторпо входу 3(3). Кодовое слово, получаемое на выходе 5, может быть представлено вектором(4),где- входной вектор длины 1, ,(информацию, которую надо закодировать), а- вектор проверочных разрядов длины 1, , (-). Так как в соответствии с 20 и в эквивалентной форме 0, то можно записать(6)),где- инверсия матрицы. Так как модуль кодирования 27 не содержит принципиально нового, схема и описание функционирования блока опущены. Для формирования проверочных матриц и хранения их представлений в запоминающем устройстве 28 выполняются предварительные вычисления. Сначала формируется базовая квадратная матрица 0 размером . Параметрможет изменяться. Базовая матрица 0 генерируется на основе известного метода 5 и является единичной. Матрица 0 может частично входить в(в этом случае будут использоваться только первыестолбов или первыестрок). В реальном устройстве необходимо выбирать 47, 87, 101 и т.д., т.е. достаточно большое. Однако для примера выберем 5. После определения матрицы базового кода строятся перестановочные матрицы на основе операции циклического сдвига столбцов влево. Операция повторяется -1 раз, что позволяет получить 1, , -1 сдвиговых матриц. 6 Полученные матрицы используются в дальнейшем для построения матрицы . Согласно 5 для размещения перестановочных матриц ввыбираются два числаи , принадлежащие ненулевым элементам поля Галуа. Тогда заполнение матрицыразмером (-) состоит в расстановке матриц , а также нулевых квадратных матриц для обеспечения заданного . В общем случае (, )-элемент матрицыравен ,(-)(-) , для,Прив матрицеотсутствуют квадратные нулевые матрицы. Если, то необходимо вводить - нулевых матриц в каждый столбец и строку подматриц матрицы . Согласно (7)(-) / , а/ . В построенной по 5 проверочной матрицедлина самого короткого цикла будет равна 6 и не потребуется выполнение схемы удаления циклов. Таким образом, результирующая проверочная матрицасодержит проверочную матрицу , получаемую в результате конкатенации нулевых и перестановочных 0, , -1 матриц, а также содержит расположенную справа двойную диагональную матрицу(прочерки в матрице означают нулевые элементы) гдедвойная диагональная матрица вида 1 0 0 0 1 1 0 0 0 0 1 1 Например, сгенерируем матрицу для кода (648, 162, 3). Пусть 47,2,5, тогда согласно (7)10,3,1/4 и матрицаразмерности 480648 будет выглядеть следующим образом (отсутствие значения всоответствует нулевым квадратным матрицам) 1 2 4 8 16 32 17 34 21 42 Для уменьшения плотности матрицы, при 2, выполним прореживание матрицы(10), используя псевдослучайный генератор. В результате получим матрицу для кода 1 2 4 825 3 6 12 При увеличении скорости кода 2/3 будет сгенерирована в соответствии с (7) матрица для кода (648, 432, 9) 7 И так далее. Тогда в соответствии с (8) проверочные биты будут вычисляться на основе соотношений где 1, 2, - - строки матрицы(здесь и далее операция- суммирование по модулю два). Проверочные битыдобавляются к информационным , образуя кодовое слово . На фиг. 3 представлена структурная схема НППЧ-декодера 16, содержащая блок декодирования 31 и оперативное запоминающее устройство 32. ЗУ 32 по структуре и содержанию аналогично ЗУ 28 НППЧ-кодера 4. С выхода 22 блока анализа 20 приемника 12 на вход ЗУ 32 подается адрес ячеек памяти, из которых должна быть считана часть проверочной матрицы (сигналы записи/считывания на фиг. 3 не указаны) и подана на второй вход 33 и третий вход 34 блока декодирования 31. Рассмотрим пример работы устройства. В начальный момент функционирования устройства, в случае отсутствия информации о качестве канала блок анализа 20 выбирает код(16 200, 14 400, 64) с 8/9. Блок контроля четности 6 добавляет -последовательность к кодовому слову. Блок модуляции/демодуляции 8 выполняет преобразование и передает информацию в беспроводной канал связи 10. На стороне приемника 12 выполняется обратное преобразование блоком модуляции/демодуляции 13 и декодирование НППЧ-декодером 16, параллельно выполняется вычислениезначения блоком контроля четности 18 и сравнение вычисленного и полученного значения , в случае несовпадения блок анализа 20 фиксирует ошибку. Блок анализа 20 накапливает значения ошибок и рассчитывает значение . Через заданное число блоков блок 20 получает значение качества канала 3.110-4, что соответствует, например, категории 3 и формирует выход 22, который поступает на второй вход НППЧ-декодера 16 и на второй вход 25 НППЧ-кодера 4, через блоки 13, 10 и 8. Тогда происходит выбор нового кода(16 200, 14 400, 128) по табл. 2 и из запоминающих устройств 28 и 32 считывается соответствующая проверочная матрица, на основе которой будут работать блок кодирования 27 НППЧ-кодера 4 и блок декодирования 31 НППЧ-декодера 16. В ходе передачи при любой категории качества канала, за исключением , анализатор увеличивает плотность проверочной матрицыи затем уменьшается скорость кода . Так последовательно может быть переключение кодера/декодера на ПНППЧ-коды (16 200,12 600, 64), (16 200, 12 600, 128), (16 200, 12 600, 256), (16 200, 10 800, 64), (16 200, 10 800, 8 82962012.06.30 128), (16 200, 10 800, 256) и т.д. В случае ухудшения, отсутствия изменений или незначительного улучшения блок анализа 20 выбирает код с длинной длиной кодового слова, т.е.изменяется с 16 200 на 64 800, и затем весь процесс повторяется снова увеличивается плотность проверочной матрицы и уменьшается скорость кода. В случае достижения приемлемого качества категорииибудет происходить обратный процесс увеличение скорости кода и уменьшение плотности проверочной матрицы. Таким образом, в процессе передачи периодически происходит пересчет значенияи переключение на различные ПНППЧ-коды. Процесс выбора параметров кода по табл. 2 в случае непрерывного ухудшения качества может быть выражен графически (фиг. 4). Здесь номер соответствует последовательности изменения параметров, а точки - начальному и конечному положению при выборе ПНППЧ-кода. На фиг. 5 представлены результаты компьютерного имитационного моделирования системы передачи информации 6, подтверждающие эффективность использования представленного устройства. Для сравнения производительности представлены результаты работы системы на основе трех различных кодов ПНППЧ, НППЧ-кода (16 200, 14 400, 16) с постоянной скоростью и НППЧ с 16 200 и переменной скоростью кодирования (скорость кодирования уменьшается с увеличениеми принимает следующие значения 8/9, 7/9, 2/3, 4/9, 3/5, 2/5, 1/3). Маркированные точки на фиг. 5, отмеченные номерами от 1 до 8, сняты в определенные промежутки времени и имеют параметры кода , , , представленные в табл. 3. Таблица 3 Значения параметров кода ПНППЧ 1 2 3 4 5 6 16 200 16 200 16 200 16 200 64 800 64 800 14 400 10 800 9720 5400 58 320 58 320 64 16 64 64 64 128 8/9 2/3 3/5 1/3 9/8 9/8 Как показывают результаты моделирования (фиг. 5), производительность предложенного метода кодирования на основе ПНППЧ-кода выше по сравнению с НППЧ-кодами. Кроме того, в случае повышения качества канала динамически устанавливается более быстрый код НППЧ, что увеличивает скорость передачи информации. Таким образом, предлагаемое адаптивное устройство кодирования/декодирования кодов низкой плотности проверок на четность выполняет те же функции, что и известное. Однако преимущество предлагаемого устройства состоит в увеличении скорости передачи за счет динамического изменения параметров кода и эффективного хранения проверочных матриц, а также в увеличении надежности передачи за счет увеличения плотности проверочных матриц и скорости кода. Это позволяет использовать в данном устройстве адаптивные ПНППЧ-коды с различной корректирующей способностью и скоростью кода в зависимости от качества канала связи (без отключения канала), что невозможно в известном устройстве 4. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 10