Конструирование новых идеальных последовательностей учетверенной длины Кренгель Е. И

Теория сигналов и систем

Конструирование новых идеальных последовательностей учетверенной длины

Кренгель Е.И.

ООО «Кедах Электроникс Инжиниринг», Россия, г. Москва

e-mail: [email protected]

1. Введение

Последовательности с идеальной периодической автокорреляционной функцией (ПАКФ) широко используются для синхронизации, оценки и измерения параметров в системах фиксированной и мобильной связи, а также в радиолокации [1-3]. В современной литературе описаны различные методы построения идеальных последовательностей с комплексно-значными и действительно-значныыми алфавитами [1,2,3]. По техническим соображениям наибольшее распространение получили идеальные многофазные последовательности Франка, Чу-Задова и Милевского [2], символы которых принадлежат множеству комплексных чисел корней из единицы. Однако у всех этих последовательностей имеется недостаток: с ростом их длины объем алфавита у них увеличивается [2].

В то же время известны многочисленные семейства идеальных многофазных последовательностей с нулями, объем алфавита которых не зависит от длины последовательностей. Это троичные последовательности Ипатова и Хохолдта-Джастесена (Hoholdt-Justesen) длины (p^mk-1)(p^m-1), k - нечетно [1,4], 4-фазные последовательности Ли (Lee) длины (p^m+1)2 mod 4 [5], 8-фазные последовательности Люке (Lüke) длины (p^m+1)4 mod 8 [6], 8-фазные последовательности длины 2(p^m+1)4 mod 8 [7] и др. [3].

Идеальные последовательности могут быть также получены за счет посимвольного перемножения идеальных последовательностей с взаимно простыми длинами [1,2]. В литературе такие последовательности получили название идеальных комбинированных последовательностей. В частности, при перемножении двух таких последовательностей, одной из которых является идеальная двоичная последовательность 1 1 1 –1, образуется идеальная последовательность учетверенной длины с тем же или удвоенным алфавитом. Надо сказать, что такой способ широко используется для формирования идеальных троичных последовательностей учетверенной длины [1].

В 2008 г. на основе смешивания идеальных многофазных и нечетно-идеальных троичных последовательностей длиныыы N с одинаковым числом нулей были получены новые идеальные последовательности учетверенной длины 4N, в том числе идеальные троичные последовательности [8], число которых во много раз превышает известные.

В настоящей работе представлен общий метод конструирования новых идеальных последовательностей учетверенной длины на основе смешивания любых двух идеальных и нечетно-идеальных последовательностей длины N с одним и тем же пиком автокорреляции.

2. Основные понятия

Последовательность x={x_i} длины N называется идеальной, если ее ПАКФ равна нулю для всех ненулевых сдвигов, почти идеальной, если ее ПАКФ равна нулю для всех ненулевых сдвигов, кроме одного и нечетно-идеальной, если ее нечетно-периодическая автокорреляционная функция для всех ненулевых сдвигов равна нулю [1,3,6,9,10].

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

Четно-нечетным преобразованием (EOT) с целым параметром t последовательности s={s_j} длины N называется линейное преобразование [11] s_jt= s_jexp(ij(2t+1)/N) всех j=0,1,2…N-1, . (1)

Пусть и есть соответственно четная (периодическая) и нечетная корреляционные функции последовательностей r и s длины N, а и соответственно четная и нечетная корреляционные функции последовательностей rt и st . Тогда согласно [11] (2)

и (3), для всех =0,1,…,N-1.

Из выражений (2) и (3) следует, что если s - нечетно-идеальная последовательность, то последовательность st является идеальной. Справедливо и наоборот, если st есть идеальная последовательность, то s - нечетно-идеальная последовательность. Заметим, что EOT преобразование является обобщением двоично-фазового преобразования (BPT) [6].
3. Конструирование идеальных последовательностей учетверенной длины

В 2007 г. Т. Хайяши (T. Hayashi) для остроения множеств последовательностей с нулевой зоной корреляции (ZCZ) предложил смешивать нечетно-идеальные и идеальные последовательности длины N с равными автокорреляционными пиками R [12]. В вышедшей в 2008 г. работе [8] было показано, что этот метод можно использовать и для построения новых идеальных многофазных последовательностей с нулями и малым алфавитом.

Идея метода состоит в следующем. Пусть a={a_j} и b={b_j} есть соответственно идеальная многофазная и нечетно-идеальная троичная последовательности длины N с одним и тем же автокорреляционным пиком R. С помощью конкатенации создаем пару последовательностей d=aa и e=b длины 2N, где . Затем, смешивая элементы последовательностей d и e, строим последовательность f длины 4N с элементами f_2j=e_j, f_2j+1=d_j, 0j<2N, которая согласно [8] является идеальной последовательностью. Заметим, что идея смешивания двух последовательностей для улучшения корреляционных свойств плодотворно использовалось и ранее, например, при синтезе троичных последовательностей с минимальными значениями боковых выбросов [13].

Рассмотрим теперь общий случай, когда в качестве исходных последовательностей a и b выбираются произвольные идеальные и нечетно-идеальные последовательности длины N с равными автокорреляционными пиками R. Нетрудно убедиться, что образованные на их основе последовательности d и e обладают следующими свойствами:

1) последовательности d и e являются не коррелированными;

2) последовательность e является почти идеальной последовательностью;

3) _d(0)=_d(N)=_e(0)=-_e(N)=2R.

Из первого свойства следует, что ПАКФ последовательности f для всех нечетных сдвигов равна нулю. В силу свойств 2 и 3 ПАКФ последовательности f для всех ненулевых четных сдвигов также оказывается равной нулю. Отсюда заключаем, что последовательность f является идеальной последовательностью.

Для построения пар исходных последовательностей a={a_j} и b={b_j} можно воспользоваться EOT преобразованием (1). При этом соответствующие пары исходных последовательностей a={a_j} и b={b_j} могут быть связаны EOT преобразованием не прямо, а через их децимации или циклические сдвиги. Однако возможны случаи, когда в качестве исходных последовательностей могут быть взяты последовательности, не связанные EOT преобразованием. Например, комбинированная идеальная последовательность длины N=q+12 mod 4, q=p^m – нечетно, полученная перемножением идеальной 4-х фазной последовательности Шоттена нечетной длины (q+1)/2 [14] и идеальной последовательности Чу длины 2, и нечетно-идеальная троичная последовательность длины N.

Обозначим через M_a и M_b соответственно общее число различных (с точностью до сдвига) идеальных и нечетно-идеальных последовательностей a и b. Из построения следует, что общее число новых идеальных последовательностей учетверенной длины может быть найдено по формуле M=NM_aM_b . (4).

Пусть последовательности a={a_j} и b={b_j} связаны между собой EOT преобразованием. Тогда в случае нечетно-идеальной троичной последовательности b=s={s_j} объем фазового алфавита последовательности a=st равен P_a=2N/НОД(2t+1,N) [3]. Очевидно, что для его минимизации необходимо максимизировать значение НОД(2t+1,N). В этом случае st={s_jexp(2ij/2^с+1)}, где 2^с+1=2N/(2t+1). Отсюда следует, что алфавит последовательности f учетверенной длины совпадает с алфавитом последовательности a.

Предположим, что последовательности a и b есть многофазные последовательности с объемом алфавитов P_a и P_b. Тогда объем фазового алфавита учетверенной последовательности f равен P_f=НОК(P_a, P_b) . (5)

Поэтому при P_b=2 объем алфавита последовательности f при нечетном P_a удваивается, а при четном остается без изменений.

4. Примеры

I. Пусть a – идеальная многофазная последовательность Франка. Известно, что последовательности Франка образуют семейство идеальных многофазных последовательностей длины N=q² и объемом алфавита q с общим членом [2] , (6), где 0n=jq+kq²-1, (r,q)=1, =e^i2/q и q -любое целое число.

Пусть q нечетно. Из (6) следует, что объем алфавита нечетно-идеальной многофазной последовательности b равен 2q. Отсюда получаем, что объем фазового алфавита последовательности f длины 4q² равен P_f=НОК(P_a,P_b)=НОК(q,2q)=2q. В результате последовательность f будет иметь точно такой же алфавит, что и последовательность Франка длины 4q² . Можно показать, что в случае четных q=2^gd, d – нечетно, объем фазового алфавита f в 2^g раз превысит объем алфавита последовательности Франка такой же длины. Пусть q=2. Последовательность Франка длины 4 есть 1 1 1 –1, а соответствующая ей нечетно-идеальная последовательность равна b={}, где . В результате получаем идеальную 8-фазную последовательность длины 16, где 0,0,0,7,0,6,4,1,0,4,0,3,0,2,4,5. Таким образом, к трем известным идеальным 8-фазным последовательностям Чу длины 4, Милевского длины 32 и Франка длины 64 добавляется новая идеальная 8-фазная последовательность длины 16.

II. Пусть a – идеальная 4-фазная последовательность Ли длины p^m+1 с одним нулем. Этой последовательности соответствует нечетно-идеальная троичная последовательность b длины p^m+1 [6]. В этом случае идеальная последовательность f будет также 4-х фазной, но уже с 4-мя нулями. В частности, если a=i -1- i 1 - i 0 – i 1 -i -1 - идеальная 4-фазная последовательности Ли длины 10, то соответствующая ей нечетно-идеальная троичная последовательность b=1 1 1 1 -1 0 1 1 -1 1. В результате получаем последовательность f=1 i 1 -1 1 - i 1 1 -1 - i 0 0 1 - i 1 1 -1 - i 1 -1 -1 i -1 -1 -1 - i -1 1 1 - i 0 0 -1 - i -1 1 1 - i -1 -1 длины 40 с 4-мя нулями. Для сравнения заметим, что комбинированная идеальная многофазная последовательность длины 40, полученная в результате перемножения последовательности Милевского длины 8 и последовательности Чу длины 5, имеет объем алфавита, равный 20.

Выводы

На основе смешивания любых двух идеальных и нечетно-идеальных последовательностей длины N с одним и тем же пиком автокорреляции построены новые идеальные последовательности учетверенной длины.

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

Литература

1. 
   Ипатов В.И. Периодические дискретные сигналы с оптимальными корреляционными свойствами.- М.: Радио и связь, 1992.
   
2. 
   Fan P. and Darnell M. Sequence Design for Communications Applications.- RSP-John Wiley & Sons Inc., London, 1996.
   
3. 
   Schotten H.D. and Luke H.D. New perfect and w-cyclic-perfect sequences. - in Proc. 1996 IEEE International Symp. Information Theory and Its Applications, Victoria, BC, Canada, September, 1996.
   
4. 
   Hoholdt T. and Justesen J. Ternary sequences with perfect periodic auto-correlation.- IEEE Trans. Inf. Theory, vol. 29, No.4, 1983, pp. 597- 600.
   
5. 
   Lee C.E. Perfect q-ary sequences from multiplicative characters over GF(p).- Electron. Lett., vol.3628,9(Ap.,1992), pp.833-835.
   
6. 
   Lüke H. D. BTP-transform and perfect sequences with small phase alphabet.- IEEE Trans. Aerosp. Electron. Syst., vol. 32, Jan.,1996, pp. 497–499.
   
7. 
   Кренгель Е.И. Новые идеальные 4- и 8-фазные последовательности с нулями.-Радиотехника, №.5, 2007, Стр. 3-7.
   
8. 
   Krengel E.I. New polyphase perfect sequences with small alpabet.- Electron. Lett., vol. 44, No.17, Aug, 2008, pp. 1013-1014.
   
9. 
   Wolfmann J. Almost perfect autocorrelation sequences. – IEEE Transaction on Information Theory, vol. IT-38, No. 4, 1992, pp. 1412-1418.
   
10. 
    Langevin P. Almost perfect binary functions. - Applicable Algebra in Engineering, Communication and Computing, 4, 1993, pp.95-102.
    
11. 
    Mow W.H. Even-odd transformation with application to multi-user CW radars.- 1996 IEEE 4 th International Simposium on Spread Spectrum Techniques and Applications Proceedings, September 22-25, Mainz, Germany, pp.191-193.
    
12. 
    Hayashi T. Zero-correlation zone sequence set construction using an even-perfect sequence and an odd-perfect sequence.- IEICE Trans Fundamentals, vol. E90-A, No.9, 2007, pp.1871-1874.
    
13. 
    Гантмахер В.Е., Едемский В.А. О синтезе дискретно-кодированных последовательностей периода 2р.- Сборник докладов 10-й международной конференции ‘Цифровая обработка сигналов и ее применение’, 26-28 марта 2008, Москва, Стр. 16-19.
    
14. 
    Lüke H. D. Almost-perfect quadriphase sequences.- IEEE Transaction on Information Theory, vol. IT-47, No. 6, 2001, pp. 2607-2608.
    

On Construction of new perfect sequences of quadruple length

Krengel E.

Kedah Electronics Engineering, Moscow, Russia,

E-mail: [email protected]

Perfect polyphase sequences with small phase alphabet are widely used in digital communication, navigation and radar engineering. A polyphase sequence is a sequence of complex numbers with unit magnitude. Unfortunately, the perfect polyphase sequences with small phase alphabet can be built only for few lengths. At the same time, perfect polyphase sequences with zeroes whose alphabet size doesn’t depend on their length have been discovered. Among them there are ternary Ipatov and Hoholdt-Justesen sequences, 4-phase Lee sequences, 8-phase Lüke sequences and etc. Recently, new perfect polyphase sequences of length 4N with zeroes and small phase alphabet have been derived from pairs of perfect polyphase sequences with zeroes and odd-perfect ternary sequences of the same length N. In the paper, we present a generalized construction method of perfect sequences of length 4N based on arbitrary pairs of perfect sequences and odd-perfect sequences with length N and the same autocorrelation peak R.

The construction method of new perfect sequences is the following. Let sequences a={a_j} and b={b_j} be accordingly an arbitrary perfect sequence and an odd-perfect sequence of length N with the same autocorrelation peak R. Then by concatenation we form two sequences d=aa and e=b of length 2N where In result the sequence f={f_k}, 0k<4N, obtained by mixing of the sequences d and e is the perfect sequence of quadruple length. To construct the reference pairs of sequences a and b we can use Even-odd transformation (EOT) which maps any odd-perfect sequence into a perfect sequence of the same length and on the contrary. The relevant sequences can be connected by EOT indirectly through their decimations or cyclic shifts. However there are cases when the relevant sequences are not connected by EOT.

Let M_p and M_o be accordingly total number of shift-distinct perfect and odd-perfect sequences of the same length N with autocorrelation peak R. Obviously, distinct pairs of these sequences and their cyclic shifts form distinct perfect sequences of quadruple length 4N. Then the total number of new shift-distinct perfect sequences of length 4N is equal to M=NM_pM_o.

Example. Let us consider the perfect binary Frank sequence a=1 1 1 –1 of length 4. By EOT build the odd-perfect ternary sequence b={} of length 4 where . In result we get the perfect 8-phase sequence f of length 16 where 0,0,0,7,0,6,4,1,0,4,0,3,0,2,4,5. Thus, we add one more perfect 8-phase sequence to the three known perfect 8-phase sequences: Chu sequence of length 4, Milewski sequence of length 32 and Frank sequence of length 64.



ЦИФРОВАЯ СИСТЕМА СЛЕЖЕНИЯ ЗА ФАЗОЙ НА ОСНОВЕ ДВУХКОЛЬЦЕВОЙ СТРУКТУРЫ

Новиков В.Ю., Казаков Л.Н.

Ярославский государственный университет им. П.Г. Демидова

Введение

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

Наиболее изученным классом СФС дискретного типа являются системы функционирующие по одношаговому рекуррентному алгоритму фильтрации [1, 2]. Суть их работы заключается в том, что после формирования на очередном шаге фильтрации оценки отслеживаемого параметра не делается попытки ее уточнения на очередном шаге и эта оценка принимается за истинное значение параметра. При этом уменьшение частоты дискретизации (для согласования с полосой обрабатываемого сигнала) приводит к ухудшению точностных характеристик. Это связано с задержкой сигнала в кольце слежения на один такт, возникающей из-за наличия интегрирующего звена с передаточной функцией 1/(z-1). Таким образом, даже оптимально спроектированные однокольцевые СФС уступают по помехоустойчивости аналоговым системам [3, 4]. Использование интегрирующего звена с передаточной функцией вида z/(z-1) снимает эту проблему, но возникает вопрос о реализуемости такой системы. Применение многошаговых алгоритмов фильтрации позволяет решить эту проблему, давая возможность ослабить, а зачастую и скомпенсировать влияние указанной задержки.

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

Система слежения за фазой

На рис. 1 представлена схема следящей ФАП [5]. Для формирования выходных отсчетов используют синфазную и квадратурную составляющие I_p и Q_p. Дискриминационная характеристика (ДХ) дискриминатора, представленного на рис. 1 имеет вид F(∆φ) = sin(∆φ), где ∆φ ­– ошибка слежения. В качестве фильтра Ф в кольце управления используются дискретные фильтры первого и второго порядка. На основе функциональной схемы (рис. 1) строится структурная схема данной однокольцевой следящей системы, которая представлена на рис. 2а), где F(∙) – дискриминационная характеристика; n(k) – аддитивный шум, пересчитанный на выход дискриминатора; θ(k) – сумма фазы полезного сигнала и фазового шума η(k); K₁, K₂ – параметры фильтра Ф. Как уже отмечалось ранее, звено 1/(z-1) приводит к нежелательной задержке, от которой можно избавиться заменой данного блока на элемент z/(z-1).



Рис. 1. Функциональная схема следящей ФАП.

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

а)	б)
Рис. 2. Структурная схемы: а) однокольцевой следящей системы, б) двухкольцевой следящей системы.

На рис. 3 представлены зависимости дисперсии ошибки слежения систем, изображенных на рис. 2а) − I и рис. 2б) ­− II. Из графиков следует, что в случае однокольцевой системы с ростом K₁ шумовая полоса растет, соответственно растет дисперсия ошибки. В случае двухкольцевой системы шумовая полоса уменьшается, соответственно уменьшается дисперсия ошибки. Этим объясняется выигрыш в дисперсии ошибки двухкольцевой системы по сравнению с однокольцевой с ростом усиления. С уменьшением K₁ этот выигрыш становится незначительным, но режим с очень низким усилением в интегрирующем канале использовать нецелесообразно по причине большой длительности переходных процессов.

а)	б)
Рис. 3. Зависимость дисперсии ошибки слежения при К2 = 1.5 для а) Dn = 0.01, Dη = 0; б) Dn = 0, Dη = 0.01.
а)	б)
Рис. 4. Зависимость среднего времени до срыва слежения от К1 при K2 = 1.5 для а) Dn = 0.1, Dη = 0; б) Dn = 0, Dη = 0.1.

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

Заключение

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

Литература

1. 
   Цифровые радиоприемные системы / Под ред. М.И. Жодзишского. – М.: Радио и связь, 1990. – 208с.
   
2. 
   Системы фазовой синхронизации с элементами дискретизации: 2-е изд., доп. и перераб. / В.В. Шахгильдян, А.А. Ляховкин, В.Л. Карякин и др.; Под ред. В.В. Шахгильдяна. – М.: Радио и связь, 1989. – 320 с.
   
3. 
   Шахтарин Б.И. Статистическая динамика систем синхронизации. – М.: Радио и связь, 1998. – 488 с.
   
4. 
   Витерби Э.Д. Принципы когерентной связи. М.: Сов. радио, 1970. – 350 с.
   
5. 
   Глобальная спутниковая радионавигационная система ГЛОНАСС / Под ред. В.Н. Харисова, А.И. Перова, В.А. Болдина. – М.: ИПРЖР, 1998. – 400 с.
   

DIGITAL PHASE TRACKING SYSTEM ON A BASE OF DUBLE-RING STRUCTURE

Novikov V., Kazakov L.

Yaroslavl State University

Nowadays-modern radiolocation, telecommunication and navigation system development is impossible without wide range of phase locked loop systems application. Practically solemn classes of such systems are phase and frequency tracking.

For their effectiveness enhancement an application of multi-loop structures is proposed. A comparative analysis of single and double loop tracking structures was performed. The results show the sufficient advantage of multi-loop systems.



АЛГОРИТМ ДЕКОДИРОВАНИЯ КОДОВ РИДА-СОЛОМОНА, ИСПРАВЛЯЮЩИЙ ВПЛОТЬ ДО n-k ОШИБОК В КОДОВОМ СЛОВЕ

Егоров С.И.

Курский государственный технический университет

I. ВВЕДЕНИЕ

Коды Рида-Соломона (РС-коды) характеризуются параметрами (n,k,d), где n – длина кодового слова, k – количество информационных символов в кодовом слове и d – минимальное кодовое расстояние. При этом количество проверочных символов в слове r = (n-k), и d = r+1. Символы кодового слова представляют собой элементы поля Галуа GF(q).

Известно, что коды Рида-Соломона могут гарантированно исправлять любой набор из t ошибочных символов, тогда и только тогда, когда выполняется условие 2t+1≤d, или . В [1] Гурасвами и Судан предложили алгоритм декодирования РС-кодов (известный как GS алгоритм), исправляющий ошибочные символы и в том случае, когда вышеприведенное неравенство нарушается (т.е. за границей половины минимального кодового расстояния). В [2] предложен алгоритм декодирования РС-кодов, позволяющий исправить t_C+1 ошибочных символов независимо от скорости кода (k/n).

В представленной работе предлагается обобщение алгоритма декодирования [2] на случай исправления большего числа ошибок за границей половины минимального кодового расстояния. Общее число исправляемых ошибочных символов может достигнуть n-k.

II. АЛГОРИТМ ДЕКОДИРОВАНИЯ

Предлагаемый алгоритм декодирования относится к методам синдромного декодирования и базируется на применении алгоритма Берлекэмпа-Месси [3]. Он предусматривает поиск локаторов t_C+τ ошибочных символов (– число гарантированно исправляемых кодом ошибок, τ – число дополнительно исправляемых ошибок) в кодовом слове, которые являлись бы обратными к корням возможного полинома локаторов ошибок степени t_C+τ. Этот полином мог бы быть получен на выходе алгоритма Берлекэмпа-Месси после 2(t_C+τ) итераций при правильном определении неизвестных невязок на последних 2τ итерациях.

Предлагаемый алгоритм декодирования предусматривает выполнение следующих этапов:

1) Вычисляется полином синдромов S(x) [3]. Если компоненты синдрома нулевые (ошибок нет), осуществляется переход к п.12.

2) Вычисляются полином локаторов ошибок , вспомогательный полином и формальная степень полинома локаторов путем выполнения 2t_C итераций алгоритма Берлекэмпа-Месси.

3) Если ≤ t_C, находятся корни полинома . Если их число равняется , то обратные к ним значения принимаются как локаторы ошибок. По формуле Форни [3] вычисляются значения ошибок. Ложная конфигурация ошибок отфильтровывается, верная добавляется в список.

4) Вычисляется управляющая переменная s (shift): s = t_C -. Если s ≥ τ или s ≤ -τ, осуществляется переход к п.11.

5) Вычисляются преобразования Фурье полиномов и .

6) Вычисляются множества значений дробей , когда s ≥ 0, или ∙в противном случае ( – примитивный элемент поля GF(q); i=0,…n-1).

7) Для v = 1,…, τ выполняются п.8 – п.10 (в каждом таком цикле находятся комбинации ошибок веса t_C + v).

8) Вычисляются вспомогательные переменные (см. п.9): l = 2v, o1 = v - |s+1|, o2 = v - |s|, w = t_C +1-v. После чего п.9 – п.10 выполняются v - |s| раз (в случае v = -s эти пункты выполняются один раз).

9) Вычисляются последовательности возможных значений невязки для всех возможных наборов индексов i₁, i₂,…,i_l-1 (i_l = i_l-1+1,…,n-1) и осуществляется поиск значений , которые встречаются точно w раз в какой-то из этих последовательностей, где



.

В тех случаях, когда при вычислении каких-то из дробей возникает деление на ноль вычисление упрощается.

Если найдены значений , которые встречаются точно w раз в какой-то из этих последовательностей, то значениями локаторов ошибок являются значения индексов i₁, i₂,…,i_l-1 этой последовательности и множество значений индекса i_l, соответствующего таким . По формуле Форни вычисляются значения ошибок. Ложные конфигурации ошибок отфильтровываются, верные добавляются в список.

10) l = l – 1, o1 = o1 – 1, o2 = o2 – 1, w = w + 1.

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

12) Конец.

Представленный алгоритм реализует списочное декодирование, он находит все кодовые слова, попавшие в сферу радиуса t+τ вокруг принятого из канала слова. Эффективность его применения может быть увеличена путем введения возможности выбора конфигурации ошибок из списка (п.11) на основе какой-либо дополнительной информации.

Асимптотическая сложность алгоритма растет полиномиально относительно n для фиксированного τ. В частности для τ = 1 она будет квадратичная, что значительно меньше в сравнении с алгоритмом Гурусвами –Судана.

III. КОРРЕКТИРУЮЩИЕ ВОЗМОЖНОСТИ РС-КОДОВ ПРИ ЖЕСТКОМ ДЕКОДИРОВАНИИэ

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

Если , в сфере не может быть более одного кодового слова. Это единственно возможный случай для классической процедуры декодирования (использующей, например, алгоритмы Берлекэмпа-Месси или Евклида), реализующей декодирование по ограниченному расстоянию t_C. Корректирующие возможности РС-кодов при использовании этой процедуры определяются минимальным кодовым расстоянием. При этом максимальное количество исправляемых ошибок равно .

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

Количество исправляемых ошибок при использовании GS-алгоритма ограничено величиной t_GS: .

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

Представленный алгоритм реализует декодирование по ограниченному расстоянию, которое может достигать величины n-k (или d-1), значительно большей t_GS. При этом важно определить, какое максимальное значение радиуса декодирования t_max имеет смысл реализовывать в алгоритме, чтобы на его выходе преобладали списки с не более чем одной конфигурацией ошибок.

Путем имитационного моделирования была выполнена оценка максимального количества ошибочных символов t_max в кодовом слове, которые исправлялись с помощью представленного алгоритма не менее чем в 80% случаев. Исследовались РС-коды, определенные над конечным полем GF(2⁸), с d = 17, и n = 55, 80, 105, 130, 155, 180, 205, 230, 255.

Для заданного РС-кода t_max определялось следующим образом. В каждом кодовом слове выборки случайным образом вносилось фиксированное количество ошибок t большее t_C, и выполнялась процедура декодирования. Если количество исправленных слов в выборке превышало 80%, число вносимых ошибок увеличивалось на единицу t = t +1, и процедура моделирования повторялась. Процесс повторялся до тех пор, пока количество исправленных слов не становилось меньше 80%. При этом в качестве t_max принималась величина t - 1.

Зависимость t_max от длины кодового слова n РС-кода приведена на следующей гистограмме (ряд 1). Также на гистограмме приведено число ошибок t_GS, которые можно исправить с помощью GS-алгоритма (ряд 2) и число гарантированно исправляемых РС-кодом ошибок t_C (ряд 3). Видно, что при укорочении кода (уменьшении его скорости) количество дополнительно исправляемых ошибок увеличивается.



Рис.1. Исправляющая способность различных алгоритмов декодирования РС-кодов над GF(2⁸) с d=17
Из гистограммы следует, что GS-алгоритм [1] не эффективен для высокоскоростных кодов (n = 105,…,255) t_GS = t_C, и в любом случае не использует всех потенциальных корректирующих возможностей рассмотренных РС-кодов t_GS < t_max.

Отметим, что алгоритм [2] обеспечивает достижение исправления t_max ошибок для РС-кодов с n = 130,…,255. В этот диапазон попадают такие важные коды как РС(204,188) и РС(255,239), широко используемые в телекоммуникационных системах.

Исправление t_max ошибок (τ = t_max – t_c > 1) для n = 105 и ниже обеспечивается представленным алгоритмом.

IV. ВЫВОДЫ

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

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

Литература

1. 
   Guruswami V., Sudan M. Improved Decoding of Reed-Solomon and Algebraic-Geometry Codes // IEEE Trans. Inform. Theory, vol. 45, no. 6, Nov. 1999, pp. 1757-1767.
   
2. 
   Egorov S., Markarian G., Pickavance K. A Modified Blahut Algorithm for Decoding Reed-Solomon Codes Beyond Half the Minimum Distance // IEEE Trans. on Commun., vol. 52, no. 12, December. 2004, pp. 2052-2056.
   
3. 
   Кларк Д. Кейн Д. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. М.: Радио и связь, 1987. 392с.
   

DECODING ALGORITHM CORRECTED UP TO N-K ERRORS IN THE CODEWORD FOR REED-SOLOMON CODES

Egorov S.

Kursk State Technical University

A Reed-Solomon (RS) code is described as an (n, k) code, where the codeword consists of n symbols from a Galois Field (GF) of q elements, k of which are information symbols. It is known that RS codes can correct any pattern of t errors or less iff 2t+1≤d (d - minimum distance). In other words, . An algorithm providing error correction beyond bounded distance for RS codes was developed by Guruswami and Sudan (GS algorithm). New decoding algorithm providing error correction up to n-k errors is proposed in this correspondence.

This algorithm bases on the Berlekamp-Massey (BM) algorithm and provides correction of t_C+τ errors by analytical continuation of the BM algorithm through 2τ more iterations having 2τ discrepancies as unknowns.

The main step of the algorithm is calculation of sequences of possible values of an unknown discrepancy:

where

,

, if ≤ t_C, and in other case, and s = t_C -;  denotes primitive element of GF; is the locator polynomial, is the auxiliary polynomial, is formal degree of , obtained as the outputs of the BM algorithm after 2t_C iterations;

In the second part of this correspondence the presented decoding algorithm was simulated for various RS codes with d=17 defined over GF(2⁸).

The proposed decoding algorithm permits to increase performance for high rate RS code. Hardware complexity of this algorithm is less in comparison with GS algorithm.



ИССЛЕДОВАНИЕ ХАОТИЧЕСКОЙ СИНХРОНИЗАЦИИ В СИСТЕМЕ СКРЫТНОЙ ПЕРЕДАЧИ ИНФОРМАЦИИ

Ходунин А.В.

Ярославский государственный университет им. П.Г. Демидова

В последние годы в научно-технической литературе появилось довольно большое число работ, авторами которых были предложены различные схемы передачи информации на основе динамического хаоса. Эти схемы можно условно объединить в несколько групп, среди которых: хаотическая маскировка (chaotic masking), переключение хаотических режимов (chaos shift keying), нелинейное подмешивание информационного сигнала к хаотическому (nonlinear signal mixing), использование структуры ФАПЧ (PLL) [1]. Интерес к теме в значительной степени определяется тем, что даже простейшие хаотические синхронизируемые системы обладают определенной степенью конфиденциальности. Речь идет о том, что посторонний наблюдатель должен обладать достаточно подробной информацией об используемой в передатчике хаотической системе, чтобы иметь потенциальную возможность для организации перехвата этой информации. С точки зрения передачи информации, можно выделить переключение хаотических режимов, как наиболее простой метод модуляции, не проигрывающий в части скрытности передачи. Он позволяет легко повышать скорость передачи, за счет увеличения позиционности. Этому способствует наличие множества слабо коррелированных хаотических режимов в рамках одного генератора хаоса при различных значениях его параметров. Рассмотрим этот метод подробнее.

Переключение хаотических режимов. На рис.1а приведена блок-схема одного из возможных вариантов подхода. Здесь передатчик представлен двумя ведущими подсистемами, в основе которых, в свою очередь, могут лежать генераторы хаоса различной или одинаковой структуры. В последнем случае они отличаются параметрами, но в интересах конфиденциальности передачи возникающие в них хаотические сигналы выбираются таким образом, чтобы они имели сходные спектральные и статистические свойства. Приемник состоит из двух ведомых подсистем, каждая из которых образует с соответствующей ведущей подсистемой пару «ведущая-ведомая». Другими словами, в основе рассматриваемого подхода лежит взаимодействие двух нар «ведущая-ведомая» подсистем. Взаимодействие происходит следующим образом.


а) б)

Рис. 1. Схемы переключения хаотических режимов (а) и структура подсистем (б)
В каждый момент времени в канал связи передается хаотический сигнал х только от одной из ведущих подсистем. С этой целью на их выходах расположены коммутирующие устройства, управляемые информационным сообщением в форме бинарного сигнала. По приходу бинарной «1» один из коммутаторов открывается и пропускает сигнал , а другой (на выходе ведущей подсистемы 2) закрывается. При появлении «0» ситуация прямо противоположная, в результате чего в канал проходит сигнал . Хаотические режимы в ведущих подсистемах должны быть выбраны так, чтобы соответствующие им сигналы приводили к появлению синхронного отклика (или синхронизации!) на выходе только своей ведомой системы. Таким образом, в зависимости от того, «0» или «1» приходят на управляющие входы коммутаторов, будет синхронизована либо одна, либо другая ведомая подсистема. Путем выявления факта синхронизации конкретной ведомой подсистемы можно определить, какой из двух битов был передан в каждый момент времени. Количество «элементарных» сигналом можно увеличивать, тем самым, повышая позиционность передаваемого кода.

В качестве ведущей и ведомой подсистем, был выбран объект – система ФАПЧ, традиционно использующийся для фазовой синхронизации регулярных сигналов. Необходимо отметить преимущество использования различных структур для приемника и передатчика, выраженное в стабильности функционирования системы при не совсем постоянных параметрах [2]. Таким образом, модель системы передачи на основе динамического хаоса основана на двух методах: переключение хаотических режимов и использование структуры ФАПЧ.

Математическая модель. В соответствии с проведенными в [3] исследованиями первая система выбрана двукольцевой (из условия максимальности области ХМК в пространстве параметров). В качестве приемника автором предложена оригинальная схема на основе двукольцевой системы ФАПЧ с едиными перестраиваемым генератором и фильтром нижних частот в цепи управления. Связь осуществляется с помощью дополнительного фазового детектора, в котором сравниваются сигналы с выходов ПГ первого кольца обеих подсистем, а результирующий сигнал, ослабленный в раз, подмешивается к сигналу с выхода ФД ведомой системы, как показано на рис.1б. Опорные генераторы выбраны с незначительной расстройкой (~ 1%), моделирующей реальную частотную расстройку. Окончательно математическая модель синхронизируемых систем связанных ФАПЧ запишется в виде

.

(1)

Под понимается фазовый белый гауссовский шум с нулевым математическим ожиданием. Система (1) определена в девятимерном цилиндрическом фазовом пространстве , которое усложняет­ся наличием периодичности за счет типа взаимосвязи. Все обозначения, а также вопросы введения понятия фаза хаотического сигнала подробно обуждаются в [4]. В силу нелинейности и высокой размерности модели её исследование выполнялось с применением численных методов. Для возможного практического внедрения необходимо, как минимум, определить среднее время вхождения систем в синхронизм, и указать допустимый уровень шумов в канале связи. Работа посвящена рассмотрению последнего вопроса.

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

а) б)

Рис. 2. Зависимости отношения усредненных частот от (а) и от ОСШ (б)
Можно заметить, что диапазон значений параметра увеличился в 4 раза по сравнению со случаем использования одиночных парциальных подсистем [3].