СПОСОБ КОДОВОЙ ЦИКЛОВОЙ СИНХРОНИЗАЦИИ
CODE FRAME SYNCHRONISATION METHOD

Изобретение относится к электросвязи и может быть использовано для цикловой синхронизации при приеме передач, использующих линейные блоковые коды произвольной длины, в условиях параметрической неопределенности относительно структуры кодера.
Известен способ кодовой цикловой синхронизации при передаче информации помехоустойчивыми блоковыми кодами (фазирование по словам), основанный на методе последовательных сдвигов, заключающийся в том, что принимаемая дискретная последовательность символов поступает на вход приемника дискретной информации, после чего производится анализ его состояния. При этом различают два состояния: синхронное, при котором точно известна информация о начале кодовых комбинаций и асинхронное, - когда информация о начале кодовых комбинаций в принимаемой последовательности неизвестна. В качестве признака синхронного состояния используется равенство нулю синдрома. В случае принятия решения об асинхронном состоянии осуществляется сдвиг на один символ по принимаемой последовательности в одну и ту же сторону. Сдвиги производятся до тех пор, пока не будут обнаруживаться только кодовые комбинации. В этом случае принимается решение о наличии синхронного состояния и процесс вхождения в синхронизм заканчивается [Лосев В.В., Бродская Е.Б., Коржик В.И. Поиск и декодирование сложных дискретных сигналов / Под ред. В.И.Коржика. - М.: Радио и связь, 1988, с.132-137].
Однако этот способ невозможно использовать в условиях параметрической неопределенности структуры кодера помехоустойчивого кода, поскольку вычисление синдрома требует знания проверочной матрицы кода или порождающего полинома [Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. - М.: Радио и связь, 1986, с.81; Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. / Под ред. К.Ш.Зигангирова. - М.: Мир, 1986, с.62-71, 116-121].
Известен способ кодовой цикловой синхронизации кодов Рида-Соломона, заключающийся в том, что принимаемая дискретная последовательность символов поступает на вход приемника дискретной информации, после чего производится анализ его состояния [Зайцев И.Е. Формирование признаков для фазирования кодов Рида-Соломона в условиях параметрической неопределенности структуры кодера - Известия вузов. Приборостроение. 1998. Т.41, №8, с.13]. При этом различают два состояния: синхронное, при котором точно известна информация о начале кодовых слов и асинхронное, - когда информация о начале кодовых слов в принимаемой последовательности неизвестна. Анализ состояния приемника основан на расчете дискретного преобразования Фурье Галуа (ДПФГ) принимаемой дискретной последовательности на длине кодового слова. В качестве признака синхронного состояния используется превышение числа нулевых компонентов в спектрах над пороговым значением. В случае принятия решения об асинхронном состоянии осуществляется сдвиг на один символ по принимаемой последовательности в одну и ту же сторону. Сдвиги производятся до установления синхронного состояния.
Однако данный способ применим только для многоосновных кодов Рида-Соломона, что не позволяет использовать данный способ применительно к линейным блоковым кодам произвольной длины.
7
Наиболее близким к предлагаемому способу является способ кодовой цикловой синхронизации всех типов циклических кодов примитивной длины, заключающийся в том, что входную дискретную последовательность символов кодовых слов циклического кода примитивной длины принимают с использованием приемника дискретной информации, после чего производят анализ его состояния. При этом различают два состояния: синхронное, при котором точно известна информация о начале кодовых слов и асинхронное, - когда информация о начале кодовых слов в принимаемой последовательности неизвестна. Анализ приемника производят по признаку синхронного состояния путем выделения из принятой дискретной последовательности фрагмента длиной, равной длине кодового слова n, и расчета ДПФГ этого фрагмента. Признаком синхронного состояния приемника дискретной информации является равенство нулю, по меньшей мере, одного спектрального компонента в спектре выделенного фрагмента. После выявления данного признака дополнительно производят проверку истинности установления синхронного состояния по наличию признака истинности фазирования. Для этого выделяют не менее четырех фрагментов той же длины, последовательно расположенных за фрагментом, выбранным на этапе определения синхронного состояния, выполняют дискретное преобразование Фурье Галуа, дополнительно выделенных фрагментов и определяют наличие признака фазирования. В качестве признака истинности фазирования используют непустое пресечение множеств номеров нулевых компонентов в полученных спектрах [Способ кодовой цикловой синхронизации: пат. 2319308 Рос. Федерация: МПК H04L 7/08 / Балунин Е.И., Дианов С.В., Тамп В.Л.; заявитель и патентообладатель Череповецкий военный инженерный институт радиоэлектроники. - №2006116215/09; заявл. 11.05.06; опубл. 10.03.08, Бюл. №7. - 1 с: ил.]. Принят за прототип.
Однако в результате имитационного моделирования работы данного способа на ЭВМ для кодовой цикловой синхронизации линейных блоковых кодов произвольной длины установлено, что данный способ применим только для циклических кодов примитивной длины.
Таким образом, недостатком прототипа (способа кодовой цикловой синхронизации на основе признака синхронного состояния приемника дискретной информации по равенству нулю, по меньшей мере, одного спектрального компонента в спектре выделенного фрагмента и признака истинности фазирования по непустому пресечению множеств номеров нулевых компонентов в полученных спектрах) является то, что он применим только для циклических кодов примитивной длины.
Технический результат - увеличение количества синхронизируемых кодов по отношению к прототипу (кодовая цикловая синхронизация линейных блоковых кодов произвольной длины) в условиях параметрической неопределенности (известны только длина кодового слова n и основание кода q) и расширение арсенала средств аналогичного назначения.
[2·n, 2·n]
[2·n,2·n]
[2·n,2·n]
[2·n,2·n]
[2·n,2·n]
[n, n]
[n, n]
[n, n]
[n, n]
Для достижения указанного технического результата в способе кодовой цикловой синхронизации входную дискретную последовательность символов кодовых слов линейного блокового кода произвольной длины n принимают с использованием приемника дискретной информации, после чего производят анализ его состояния. При этом различают два состояния: синхронное, при котором точно известна информация о начале кодовых слов и асинхронное, - когда информация о начале кодовых слов в принимаемой последовательности неизвестна. Анализ состояния приемника производят по признаку синхронного состояния. Для этого 2·n последовательно выделенных из принятой дискретной последовательности фрагментов длиной 2·n записывают в строки матрицы Y, приводят ее элементарными операциями над строками к матрице Y' в канонической ступенчатой форме [Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976, с.43-45; Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. / Под ред. К.Ш.Зигангирова. - М.: Мир, 1986, с.52-53], перестановкой строк матрицы Y' получают матрицу Y'', в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца, и разбивают матрицу Y''на четыре подматрицы A, B, C, D.
.
[n,n]
[n,n]
[n,n]
[n,n]
Признаком синхронного состояния приемника дискретной информации является равенство матриц A и B между собой, а также равенство C и D нулевой матрице размера n×n.
[2·n, 2·n],
[2·n,2·n]
[2·n,2·n]
[2·n,2·n]
[n,n]
[n,n]
[n,n]
[n,n]
При отсутствии синхронизации (асинхронном состоянии приемника) до ее установления производят поиск синхронного состояния. Для этого производят последовательный сдвиг по принимаемой последовательности на один символ в одну и ту же сторону, построение новой матрицы Yприведение ее элементарными операциями над строками к матрице Y' в канонической ступенчатой форме, получение из матрицы Y' перестановкой ее строк матрицы Y'', в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца, формирование четырех подматриц A, B, C, D и определение наличия синхронного состояния приемника по признаку синхронного состояния.
Общим с прототипом является то, что с использованием приемника дискретной информации принимают входную последовательность, представляющую собой последовательно передаваемые символы кодовых слов, выделяют фрагменты дискретной последовательности и определяют наличие синхронного состояния приемника дискретной информации по признаку синхронного состояния. При отсутствии синхронизации до ее установления производят поиск синхронного состояния путем последовательного сдвига по принимаемой последовательности на один символ в одну и ту же сторону с последующим выделением новых фрагментов и определением наличия синхронного состояния приемника по признаку синхронного состояния.
[2·n, 2·n]
[2·n, 2·n]
[2·n,2·n]
[2·n,2·n]
[2·n,2·n]
[2·n,2·n]
[n,n]
[n,n]
[n,n]
[n,n].
[n,n]
[n,n]
[n,n]
[n,n]
Отличием от прототипа является то, что для принятия решения о наличии признака синхронного состояния приемника дискретной информации формируют квадратную матрицу Y размером (2·n)×(2·n), строками которой являются последовательно выделенные из принятой дискретной последовательности 2·n фрагментов длиной 2·n. Приводят матрицу Yэлементарными операциями над строками к матрице Y' в канонической ступенчатой форме, перестановкой строк матрицы Y' получают матрицу Y'', в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца. Разбивают матрицу Y'' на четыре подматрицы A, B, C, D В качестве признака синхронного состояния используют равенство подматриц A и B между собой, а также равенство C и Dнулевой матрице размера n×n. После выявления данного признака считают, что синхронное состояние достигнуто. В случае отсутствия признака синхронного состояния, поиск синхронного состояния возобновляют с момента выделения из принятой дискретной последовательности фрагментов длиной 2·n.
Благодаря новой совокупности существенных признаков технический результат проявляется в возможности кодовой цикловой синхронизации линейных блоковых кодов произвольной длины.
k
[k,n]
[k,n]
[k,n]
[k,n]
Известно [Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976, с.52-54; Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. / Под ред. К.Ш.Зигангирова. - М.: Мир, 1986, с.61-63], что линейный блоковый (n, k) код с длиной кодового слова n, основанием q и числом кодовых слов q, где k - число информационных символов в кодовом слове, является пространством строк порождающей матрицы G и образует векторное подпространство размерности k в пространстве размерности n над полем Галуа GF(q). Размерность подпространства определяется числом линейно независимых строк (рангом) матрицы G и равна k. Результатом умножения информационной комбинации на порождающую матрицу G является кодовое слово. При этом [Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976, с.43; Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. / Под ред. К.Ш.Зигангирова. - М.: Мир, 1986, с.54] если матрица  получается из матрицы G с помощью элементарных операций над строками, то пространства строк этих матриц совпадают.
[2·k, 2·n]
Путем непосредственных вычислений установлено, что результатом умножения комбинации из двух информационных слов на матрицу Хявляется комбинация из двух кодовых слов линейного блокового кода.
,
[k,n]
[k,n]
[k,n]
[2·k, 2·n]
[2·k, 2·n]
[k, n]
[2·k, 2·n]
2·k
где подматрицы G - порождающие матрицы линейного блокового кода, имеющие ранг равный k, а O - нулевые подматрицы. Так как ранг матрицы G равен k, то ранг матрицы Хравен 2·k. Следовательно, пространство строк матрицы Химеет размерность 2·k, содержит q кодовых комбинаций, состоящих из любых двух кодовых слов линейного блокового кода длины n с порождающей матрицей G и является векторным подпространством размерности 2·k в пространстве размерности 2·n над полем Галуа GF(q). При этом [Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра: Учебник. В 2-х т. T.I. - М.: Гелиос АРВ, 2003, с.152-153] если размерность подпространства равна 2·k, то любая линейно независимая система векторов (кодовых комбинаций) из данного подпространства (пространства строк матрицы Х) содержит не более 2·k векторов, любая такая система из 2·k векторов является его базисом и любые два его базиса равномощны.
[k,n]
[k,k]
[k·n]
[2·k, 2·n]
Если линейный блоковый код является систематическим [Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976, с.58; Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. / Под ред. К.Ш.Зигангирова. - М.: Мир, 1986, с.65], то матрица G в первых k столбцах содержит единичную подматрицу I размером k×k. Следовательно, подматрицы G и матрица Х уже имеют каноническую ступенчатую форму:
.
[2·k, 2·n]
[k,n]
[2·k,2·n]
В случае несистематического кода, элементарными операциями над строками матрицы Х каждая подматрица G может быть приведена к матрице  в канонической ступенчатой форме, а матрица Х - к матрице  в канонической ступенчатой форме:
[2·k,2·n]
[2·k,2·n]
Добавив в матрицу  2·(n-k) нулевых строк таким образом, чтобы первый ненулевой элемент каждой ненулевой строки находится на главной диагонали, получим квадратную матрицу , в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца. Так как матрица  получена из матрицы Х элементарными операциями над строками, а строки матриц  и  образуют одно и то же множество всевозможных линейных комбинаций, то пространства строк матриц Х,  и  совпадают и имеют размерность 2·k. Матрица  содержит четыре квадратные подматрицы , , , .
При этом подматрицы  и  равны между собой, а подматрицы  и  равны нулевой матрице размера n×n.
[2·n,2·n]
[2·n, 2·n]
[2·n,2·n]
[2·n,2·n]
[2·n,2·n]
[2·n,2·n]
[2·n, 2·n]
[n,n]
[n,n]
[n,n]
[n,n]
Таким образом, если приемник находится в синхронном состоянии, то матрица Yв качестве строк содержит только кодовые комбинации из пространства строк матрицы . Так как число линейно независимых строк матрицы Yне может превышать числа линейно независимых строк матрицы  и обе матрицы в качестве строк содержат векторы одного векторного пространства, то пространство строк матрицы Yсодержится (образует подпространство) в пространстве строк матрицы  [Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. / Под ред. К.Ш.Зигангирова. - М.: Мир, 1986, с.45]. При этом, если любые 2·k из 2·n строк матрицы Yокажутся линейно независимыми, то размерность пространства строк матрицы Y будет равна 2·k и пространства строк матриц  и Yсовпадут [Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976, с.42]. После приведения матрицы Yэлементарными преобразованиями строк к матрице  в канонической ступенчатой форме, матрица  в первых 2·k строках будет содержать подматрицу размера (2·k)×(2·n), равную матрице , так как каждому заданному пространству строк соответствует только одна матрица в канонической ступенчатой форме [Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. - М.: Мир, 1976, с.45]. Перестановка строк матрицы  такая, что первый ненулевой элемент каждой ненулевой строки будет находиться на главной диагонали, позволит получить матрицу , в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца и равную . Следовательно, свойство матрицы  заключающееся в равенстве между собой подматриц А и B, равенстве подматриц C и Dнулевой матрице размера n×n, позволяет синхронизировать приемник дискретной информации по словам линейного блокового кода произвольной длины n.
m
m
[2·m·n,2·m·n]
[2·m·n,2·m·n]
[m·n,m·n],
[m·n,m·n]
[m·n,m·n],
[m·n,m·n]
При синхронизации многоосновных (q=p, p - простое число, m≥2) линейных блоковых кодов элементы кодовых слов (n, k) кода, заданные над расширенным полем Галуа GF(p), допускают представление в виде p-ичных m-разрядных векторов. Такого рода отображение представляет собой линейный блоковый код с параметрами (n·m, k·m), где m - степень расширения поля исходного кода [Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. - М.: Связь, 1979, с.291]. Это позволяет осуществлять синхронизацию приемника дискретной информации при приеме передач, использующих многоосновные линейные блоковые коды. В этом случае число строк и столбцов матрицы, формируемой из принимаемой дискретной последовательности, увеличивают в m раз, т.е. строят матрицу Y. Элементарными операциями над строками матрицы Y приводят ее к матрице  в канонической ступенчатой форме, перестановкой строк матрицы  получают матрицу , в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца. Разбивают матрицу  на четыре подматрицы A B, C D:
Признаком синхронного состояния при поиске синхронного состояния считают равенство подматриц  и  между собой, а также равенство подматриц  и  нулевой матрице размера (m·n)×(m·n).
Проведенный анализ уровня существующей техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, которые тождественны всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного способа условию патентоспособности «новизна». Результаты поиска известных решений в данной и смежной областях техники с целью выявления признаков, совпадающих с отличными от прототипа признаками заявленного объекта показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».
Заявленный способ поясняется иллюстрацией, на которой изображена структурная схема способа кодовой цикловой синхронизации.
Способ кодовой цикловой синхронизации линейных блоковых кодов любой длины в условиях параметрической неопределенности (известна длина кодового слова n и основание кода q) осуществляется следующим образом:
Этап 1. Дискретную последовательность символов кодовых слов линейного блокового кода принимают с использованием приемника дискретной информации.
Данный этап может быть реализован с помощью специализированных средств цифровой обработки сигналов или программно на ЭВМ.
Далее производят анализ состояния приемника дискретной информации (этапы 2-5).
Этап 2. Выделяют из принятой дискретной последовательности 2·n фрагментов длиной 2·n и формируют на их основе матрицу вида:
[2·n,2·n]
ij
Y=[y]=(i=1,2, …, 2·n; j=1,2, …, 2·n).
[2·n,2·n]
Этап 3. Приводят матрицу Y элементарными преобразованиями строк к матрице  в канонической ступенчатой форме. Перестановкой строк матрицы  получают матрицу , в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца.
n,n
[n,n]
[n,n]
[n,n]
Этап 4. Определяют наличие синхронного состояния приемника дискретной информации по признаку синхронного состояния. В качестве признака используют равенство подматриц А[] и В между собой, а также равенство Си Dнулевой матрице размера n×n, где
.
Этап 5. Если признак синхронного состояния выявлен, то считают, что приемник синхронизирован с началом кодовой комбинации, в противном случае продолжают поиск синхронного состояния (переход на этап 6).
Этап 6. Если признак синхронного состояния не выявлен, то осуществляют сдвиг на один символ по принимаемой последовательности и заново анализируют состояние приемника (возвращаются на этап 2).
Этапы 2-6 могут быть реализованы с помощью специализированных вычислителей или программно на ЭВМ.
Для исследования возможности осуществления предложенного способа на ПЭВМ проведено имитационное моделирования его работы. Программа написана на языке Delphi 7.0.
Результат решения контрольного примера с помощью имитационной модели выглядит следующим образом. Например, приемник дискретной информации принимает двоичную (q=2) дискретную последовательность символов кодовых слов линейного блокового кода с длиной кодового слова n=7:
тип кода, начало f кодового слова неизвестны. Синхронизируем приемник по границам кодовых слов (найдем f).
[14,14]
Проанализируем состояние приемника дискретной информации. Для этого из дискретной последовательности x, начиная с первого (f=1) символа последовательно выделяем 14 фрагментов длины 14, записываем их в строки матрицы Y:
[14, 14]
Элементарными преобразованиями строк матрицы Y приводим ее к матрице в канонической ступенчатой форме:
Перестановкой строк матрицы  получаем матрицу , в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца. Затем проверяем наличие признака синхронного состояния:
[7,7]
[7,7]
[7,7]
[14,14]
Т.к. подматрицы А и В не равны между собой, а подматрица D не равна нулевой матрице размера 7×7, то осуществляем сдвиг по дискретной последовательности x на один символ (f=2) и формируем новую матрицу Y:
[14,14]
Элементарными преобразованиями строк матрицы Y приводим ее к матрице  в канонической ступенчатой форме:
Перестановкой строк матрицы  получаем матрицу , в которой первый ненулевой элемент каждой ненулевой строки равен единице, находится на главной диагонали и является единственным ненулевым элементом своего столбца. Затем проверяем наличие признака синхронного состояния:
[7,7]
[7,7]
[7,7]
[7,7]
Поскольку подматрицы А и В равны между собой, а подматрицы С и D равны нулевой матрице размера 7×7, считаем, что приемник дискретной информации синхронизирован по границам кодовых слов (f=2).