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

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


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


Конструирование новых идеальных последовательностей учетверенной длины Кренгель Е.И. ООО «Кедах Электроникс Инжиниринг», Россия, г. Москва e-mail: evgeniy.krengel@kedah.ru
1. Введение

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

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

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

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

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

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

Четно-нечетным преобразованием (EOT) с целым параметром t последовательности s={sj} длины N называется линейное преобразование [11] sjt= sjexp(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={aj} и b={bj} есть соответственно идеальная многофазная и нечетно-идеальная троичная последовательности длины N с одним и тем же автокорреляционным пиком R. С помощью конкатенации создаем пару последовательностей d=aa и e=b длины 2N, где . Затем, смешивая элементы последовательностей d и e, строим последовательность f длины 4N с элементами f2j=ej, f2j+1=dj, 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={aj} и b={bj} можно воспользоваться EOT преобразованием (1). При этом соответствующие пары исходных последовательностей a={aj} и b={bj} могут быть связаны EOT преобразованием не прямо, а через их децимации или циклические сдвиги. Однако возможны случаи, когда в качестве исходных последовательностей могут быть взяты последовательности, не связанные EOT преобразованием. Например, комбинированная идеальная последовательность длины N=q+12 mod 4, q=pm– нечетно, полученная перемножением идеальной 4-х фазной последовательности Шоттена нечетной длины (q+1)/2 [14] и идеальной последовательности Чу длины 2, и нечетно-идеальная троичная последовательность длины N.

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

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

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

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

4. Примеры

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

Пусть q нечетно. Из (6) следует, что объем алфавита нечетно-идеальной многофазной последовательности b равен 2q. Отсюда получаем, что объем фазового алфавита последовательности f длины 4q2 равен Pf=НОК(Pa,Pb)=НОК(q,2q)=2q. В результате последовательность f будет иметь точно такой же алфавит, что и последовательность Франка длины 4q2 . Можно показать, что в случае четных q=2gd, d – нечетно, объем фазового алфавита f в 2g раз превысит объем алфавита последовательности Франка такой же длины. Пусть 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-фазная последовательность Ли длины pm+1 с одним нулем. Этой последовательности соответствует нечетно-идеальная троичная последовательность b длины pm+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 с одним и тем же пиком автокорреляции построены новые идеальные последовательности учетверенной длины.

Полученные последовательности позволяют существенно увеличить число идеальных последовательностей и в ряде случаев имеют меньший объем алфавита по сравнению с известными идеальными последовательностями.
Литература
Ипатов В.И. Периодические дискретные сигналы с оптимальными корреляционными свойствами.- М.: Радио и связь, 1992.

Fan P. and Darnell M. Sequence Design for Communications Applications.- RSP-John Wiley & Sons Inc., London, 1996.

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.

Hoholdt T. and Justesen J. Ternary sequences with perfect periodic auto-correlation.- IEEE Trans. Inf. Theory, vol. 29, No.4, 1983, pp. 597- 600.

Lee C.E. Perfect q-ary sequences from multiplicative characters over GF(p).- Electron. Lett., vol.3628,9(Ap.,1992), pp.833-835.

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.

Кренгель Е.И. Новые идеальные 4- и 8-фазные последовательности с нулями.-Радиотехника, №.5, 2007, Стр. 3-7.

Krengel E.I. New polyphase perfect sequences with small alpabet.- Electron. Lett., vol. 44, No.17, Aug, 2008, pp. 1013-1014.

Wolfmann J. Almost perfect autocorrelation sequences. – IEEE Transaction on Information Theory, vol. IT-38, No. 4, 1992, pp. 1412-1418.

Langevin P. Almost perfect binary functions. - Applicable Algebra in Engineering, Communication and Computing, 4, 1993, pp.95-102.

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.

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.

Гантмахер В.Е., Едемский В.А. О синтезе дискретно-кодированных последовательностей периода 2р.- Сборник докладов 10-й международной конференции ‘Цифровая обработка сигналов и ее применение’, 26-28 марта 2008, Москва, Стр. 16-19.

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: evgeniy.krengel@kedah.ru

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={aj} and b={bj} 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={fk}, 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 Mpand Mo beaccordingly 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=NMpMo.

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]. Для формирования выходных отсчетов используют синфазную и квадратурную составляющие Ip и Qp. Дискриминационная характеристика (ДХ) дискриминатора, представленного на рис. 1 имеет вид F(∆φ) = sin(∆φ), где ∆φ ­– ошибка слежения. В качестве фильтра Ф в кольце управления используются дискретные фильтры первого и второго порядка. На основе функциональной схемы (рис. 1) строится структурная схема данной однокольцевой следящей системы, которая представлена на рис. 2а), где F(∙) – дискриминационная характеристика; n(k) – аддитивный шум, пересчитанный на выход дискриминатора; θ(k) – сумма фазы полезного сигнала и фазового шума η(k); K1, K2 – параметры фильтра Ф. Как уже отмечалось ранее, звено 1/(z-1) приводит к нежелательной задержке, от которой можно избавиться заменой данного блока на элемент z/(z-1).



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

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




а)



б)

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


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



а)



б)

Рис. 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 систем слежения. Здесь так же наблюдается выигрыш двухкольцевой системы по отношению к однокольцевой. Следует отметить, что двухкольцевая система слежения качественнее отрабатывает аддитивное воздействие – улучшение качества работы при воздействии фазового шума менее значительно по сравнению с функционированием системы слежения в условиях аддитивной помехи. Это объясняется нелинейными эффектами, поскольку отсчеты аддитивного шума поступают на вход фильтра в цепи управления не подвергаясь нелинейным преобразованиям, в отличие от отсчетов фазового шума, поступающим на вход дискриминатора, имеющего нелинейную характеристику.

Заключение

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

Литература

Цифровые радиоприемные системы / Под ред. М.И. Жодзишского. – М.: Радио и связь, 1990. – 208с.

Системы фазовой синхронизации с элементами дискретизации: 2-е изд., доп. и перераб. / В.В. Шахгильдян, А.А. Ляховкин, В.Л. Карякин и др.; Под ред. В.В. Шахгильдяна. – М.: Радио и связь, 1989. – 320 с.

Шахтарин Б.И. Статистическая динамика систем синхронизации. – М.: Радио и связь, 1998. – 488 с.

Витерби Э.Д. Принципы когерентной связи. М.: Сов. радио, 1970. – 350 с.

Глобальная спутниковая радионавигационная система ГЛОНАСС / Под ред. В.Н. Харисова, А.И. Перова, В.А. Болдина. – М.: ИПРЖР, 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] предложен алгоритм декодирования РС-кодов, позволяющий исправить tC+1 ошибочных символов независимо от скорости кода (k/n).

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

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

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

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

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

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

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

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

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

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

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

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

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



.

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

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

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

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

12) Конец.

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

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

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

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

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

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

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

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

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

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

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

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



Рис.1. Исправляющая способность различных алгоритмов декодирования РС-кодов над GF(28) с d=17


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

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

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

^ IV. ВЫВОДЫ

Представленный алгоритм декодирования позволяет значительно повысить эффективность примене