Способ определения параметров помехоустойчивого кода

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

 

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

Известен метод идентификации параметров помехоустойчивого кода, позволяющий определить проверочную матрицу с последующим выявлением длины информационной и проверочной частей кода (Грантмахер Ф.Р. Теория матриц - 4-е изд. - М.: Наука, 1988. - 39 с.).

Метод основан на использовании алгоритма Гаусса. Из множества реализаций кодовых последовательностей формируется матрица размерности k'×n', где k' - размерность матрицы по вертикали, n' - предполагаемая длина кода, причем k'≥k, где k - длина информационной части предполагаемого кода. Полученную матрицу с использованием алгоритма Гаусса приводят к верхнетреугольной форме, затем к нижнетреугольной. Если матрица была составлена из линейно-независимых строк, то результатом работы алгоритма Гаусса служит формирование единичной матрицы In'×n', что свидетельствует об отсутствии помехоустойчивого кода с заданным параметром n', следовательно, данный параметр необходимо изменить и снова выполнить процедуры преобразования к верхнетреугольной форме, затем к нижнетреугольной. В противном случае результирующая матрица будет состоять из двух частей: единичной матрицы Ik×k и области проверок Pk×(n-k), что позволяет определить длину кода n, длину информационной части k и исправляющую способность кода t. Полученная матрица называется порождающей матрицей кода. Операция транспонирования области проверок с добавлением единичной матрицы I(n-k)×(n-k) позволяет получить проверочную матрицу необходимую для декодирования кодовых последовательностей исходного кода.

Недостатком данного метода является низкая производительность системы приема информации при наличии ошибок в цифровом потоке, из которого формируется анализируемая матрица.

Наиболее близким по своей сущности к заявляемому изобретению (прототипом) является способ автоматического выбора исходного помехоустойчивого кода и устройства для его декодирования (см. патент РФ №2271604, МПК Н03М 13/00, G06F 11/00, опубл. 10.03.2006), заключающийся в том, что для каждого из заранее заданного набора помехоустойчивых кодов с известными параметрами вычисляют значения синдромов кодовых слов, сохраняют их в память, затем по принятой реализации с учетом последовательности мягких решений вычисляют значение синдрома и сравнивают его со значениями из памяти и код с наиболее близким значением синдрома является исходным помехоустойчивым кодом с известной проверочной матрицей.

Недостатком данного способа является низкая производительность системы приема информации в виду отсутствия возможности определения параметров помехоустойчивого кода (Н - проверочная матрица кода, n - длина кодового слова, k - длина информационной части кодового слова, t - исправляющая способность кода), если исходный код не присутствует в заданном списке кодов.

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

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

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

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

Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на решение указанной задачи. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».

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

Заявленный способ поясняется чертежами, на которых показаны:

фиг. 1 - алгоритм, реализующий способ определения параметров помехоустойчивого кода;

фиг. 2 - графическое представление фрагмента нижнетреугольной матрицы;

фиг. 3 - график зависимости числа найденных проверочных уравнений W от числа итераций Q при фиксированной вероятности битовой ошибки на выходе демодулятора Р.

На фиг. 1 представлена последовательность операций способа определения параметров помехоустойчивого кода. По принятой реализации кодового слова V0 (блок A1), с учетом последовательности мягких решений, рассчитывают синдром кодового слова (блок А2). Затем полученное значение синдрома в блоках А3-А5 сравнивается с пороговыми значениями из заданного списка, формируемого на предварительном этапе (блоки А6-А8), и код, для которого число ненулевых синдромов окажется меньше порогового значения, считается исходным помехоустойчивым кодом с известной проверочной матрицей и другими параметрами. Если решающее правило не было выполнено, следовательно, анализируемый помехоустойчивый код отсутствует в заданном списке кодов и для определения параметров кода необходимо использовать основы матричного анализа. Для этого выполняется процедуры накопления кодовых реализаций (блок А11) и формирования анализируемой матрицы требуемой размерности (блок А12). При этом параметр длины кодового слова инициализируется в блоке А9 и принимает начальное значение, наиболее вероятное для данного кода (блок А10). Затем полученную матрицу с использованием алгоритма Гаусса приводят к нижней треугольной форме (фиг. 2), формируя при этом матрицу предполагаемых проверочных уравнений кода (блок А13). После чего в преобразованной матрице в области проверок определяют вес столбцов (блок А14). Затем сравнивают вес каждого столбца с пороговым значением (блоки А15-А17). Если вес столбца не превышает порогового значения, то индекс столбца определяет истинное проверочное уравнение кода в матрице предполагаемых проверок. В блоке A18 проверяется, было ли найдено хотя бы одно проверочное уравнение Р. Если не было найдено ни одного проверочного уравнения, то необходимо вернуться к блоку А10 и повторить описанную последовательность действий, выбрав другую предполагаемую длину кодовых слов (увеличить значение n на единицу). Следует отметить, что если накопленные реализации кодовых последовательностей не содержат ошибки, то все веса столбцов будут меньше порогового значения. В противном случае будут найдены не все проверочные уравнения (блок A19). В данном случае выполняется процедура декодирования накопленных кодовых реализаций с использованием уже найденных проверочных уравнений кода и алгоритма итеративного распространения доверия (блок А20). Затем снова формируется анализируемая матрица, но уже с исправленными кодовыми последовательностями и снова повторяется вся последовательность действий, представленная блоками А13-А21.

Требуемая размерность анализируемой матрицы, формируемой в блоке А12, определяется, в первую очередь, допустимыми вероятностями «пропуска цели» и «ложной тревоги» при нахождении конкретного проверочного уравнения и выражается через количество линейно-независимых кодовых слов, необходимых для восстановления всех проверочных уравнений:

где pnd - вероятность «пропуска цели» при обнаружении строки проверочной матрицы; - вероятность «ложной тревоги» при обнаружении строки проверочной матрицы; ε - вероятность битовой ошибки в канале связи; ωtH(h) - вес строки проверочной матрицы с использованием метрики Хэмминга; φ-1 - обратная функция Лапласа, табличная величина.

На практике, зачастую, отсутствуют сведения о весе строки проверочной матрицы, что затрудняет использование формулы (1), в этом случае будет М определяться объемом доступной реализации, но для эффективной работы необходимо, чтобы выполнялось следующее требование: М≥10k, где k - длина информационной части кодового слова.

Матрица предполагаемых проверочных уравнений в блоке А13 формируется следующим образом. Из матрицы, полученной в блоке А12, берется подматрица, содержащая проверочную часть кодовых слов, размерности k×(n-k), где k - длина информационной части кодового слова, n - длина кодового слова, выраженные в битах. Затем параллельно с процедурой приведения матрицы к нижней треугольной форме методом Гаусса, при сложении по модулю двух ее столбцов, также складываются строки, выбранной отдельно вышеупомянутой подматрицы, с соответствующими столбцам номерами, если они удовлетворяют условию - номер складываемого столбца меньше k. Матрица предполагаемых проверочных уравнений получается путем конкатенации полученной транспонированной подматрицы с единичной матрицей той же размерности.

Пороговое значение Т, используемое в качестве критерия при нахождении проверочных уравнений, определяется формулой

где - вероятность «ложной тревоги» при обнаружении строки проверочной матрицы; М - число строк нижнетреугольной матрицы; φ-1 - обратная функция Лапласа (табличная величина).

Эмпирическим путем установлено, что при выборе порога Т, равного 0.05×М, вероятность «ложной тревоги» при обнаружении проверочного уравнения кода стремится к нулю.

Для проверки эффективности заявляемого способа были сформированы выборки из 10240 кодовых слов низкоплотностного кода (512, 256), представленных последовательностями мягких решений, полученных при демодуляции четырехпозиционного фазоманипулированного сигнала с различным уровнем аддитивного белого гауссовского шума. Внесение шума позволило получить вероятности битовых ошибок на выходе демодулятора 2,6Е-3, 2,3Е-3 и 1,8Е-3. График зависимости числа найденных проверочных уравнений W (всего 256) от числа итераций Q при фиксированной вероятности битовой ошибки Р на выходе демодулятора представлен на фиг. 3. Результаты моделирования показывают, что с увеличением вероятности ошибки в цифровом потоке восстановление проверочной матрицы происходит за большее число итераций.

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

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



 

Похожие патенты:

Группа изобретений относится к области связи и может быть использована для передачи и приема информации в вещательной системе/системе связи. Техническим результатом является обеспечение стабильности системы.

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

Изобретение относится к технике связи и предназначено для передачи и приема в системах связи/радиовещания. Технический результат - повышение надежности связи и широковещания за счет эффективного восстановления искаженной информации.

Группа изобретений относится к области кодирования/декодирования и может быть использована для передачи и приема данных в беспроводной связи. Техническим результатом является обеспечение возможности кодировать/декодировать потоки информационных битов различных длин и одновременно поддерживать оптимальную производительность.

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

Группа изобретений относится к области передачи данных и может быть использована для кодирования/декодирования с использованием кода LDPC. Техническим результатом является повышение устойчивости к ошибкам данных.

Изобретение относится к системе связи, использующей коды Контроля Четности с Низкой Плотностью (Low-Density Parity-Check, LDPC). Техническим результатом является повышение производительности канального декодирования в системе связи, где применяются LDPC-коды.

Изобретение относится к области телемеханики, автоматики и вычислительной техники и предназначено для использования в устройствах хранения и передачи информации.

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

Изобретение относится к вычислительной технике. Технический результат заключается в обеспечении повышенной способности к коррекции ошибок.

Группа изобретений относится к области цифровой обработки информации, а именно к декодерам LDPC (кодов с малой плотностью проверок на четность) и способам их функционирования. Техническим результатом является уменьшение аппаратных ресурсов. Сущность заявленных изобретений заключается в оптимизации схемы декодера и способа его функционирования, а именно использования для каждой проверочной вершины одного узла поиска минимумов (509) и элементов памяти (503) для всех ребер, исходящих из этой проверочной вершины (502) к символьным (501) согласно графу. Для каждой символьной вершины используют один общий сумматор (516) всех сообщений (520 и 515) от проверочных вершин согласно графу Таннера и элемент памяти (524) вне зависимости от ребер, исходящих из этой символьной вершины. 2 н.п. ф-лы, 5 ил.

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

Изобретение относится к вычислительной технике. Технический результат заключается в обеспечении повышенной способности к коррекции ошибок. Способ кодирования для выполнения сверхточного кодирования на основе разреженного контроля по четности (LDPC-CC) с изменяющимся во времени периодом q с использованием полинома контроля по четности со скоростью кодирования (n-1)/n, в котором принимают информационную последовательность в качестве входных данных; и кодируют информационную последовательность с использованием уравнения 1 в качестве полинома контроля по четности #g, чтобы удовлетворять 0, причем #g является g-ым порядковым номером изменяющегося во времени периода q: (уравнение 1). 4 н. и 4 з.п. ф-лы, 75 ил., 9 табл.

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

Наверх