Крук Е.А. (ред.) Исследование LDPC кодов. Сборник статей. Часть 2

Подождите немного. Документ загружается.

2( 2) ( 2)

(1)

( 2)(2 2) ( 2)( 2)

(1) (1) ;

ak ak

vrr

ak aak ak ak

rr rr

3 4 3 4

6 446

7 8

9 

3 44433443

6 4 6 4

0;v

(2)(2)

(1) 0;

ak ak

12 21

a = k–2 или a = 2–k.

В точке a = k–2 размер алфавита достигает своего минимума, а в

точке a = 2–k – максимума.

Следовательно, для получения CFF на кодах, исправляющих ошиб&

ки, с минимальным достижимым размером алфавита необходимо брать

коды, лежащие на границе Грайсмера, с расстоянием d = (k–2)q.

Оценим размер алфавита, получаемого при использовании кодов,

лежащих на границе Грайсмера, с расстоянием d = (k–2)q:

( 2) 2 2 ( 2) 2( 2) ( 2)( 2);nk qk k k q k k q1 2 3 2 3 2 1 2 3 2 1 2 3

1 ( 2)( 2) 1 ( 2)( 2) 1

(2)(2)(2) 2(2)

21 2

22(2)2 2

nkq kq

nd k q k q k

qqq

1121121

33 3 3

1 1 211 1

31 413

2;qr1

( 2)( 2) ( 2)(2 2)2

log

4( 1)( 2) 4( 1) .

1log

vnq k q q k r r

rr k rr

112342 3 1

1 321 3

Полученный результат совпадает с теоретической границей, ко&

торую мы специально напомнили в начале раздела, с точностью до

константы. Следовательно, используя коды, лежащие на границе

Грайсмера, мы можем получить оптимальные, с точки зрения разме&

ра алфавита, CFF&схемы.

Практически, на эллиптических кривых можно построить следу&

ющие коды для конкретных параметров: q = 64, k = 13, d = 66, n = 79,

из этого кода можно получить CFF c параметрами 6&CFF (5056, 2

);

q = 53, k = 14, d = 81, n = 97, из этого кода можно получить CFF

c параметрами 6&CFF (5141, 2

). Лучшая известная до сих пор схема

на кодах Рида–Соломона дает код: q = 73, k = 13, d = 61, n = 73, из

этого кода можно получить CFF c параметрами 6&CFF (5329, 2

Способы построения кодов на границе Грайсмера

Существует несколько подходов к построению кодов на границе

Грайсмера. В 1965 году Solomon and Stiffler [15] предложили способ

построения целого класса кодов, лежащих на границе Грайсмера, с

использованием процедуры вычеркивания столбцов из порождающей

матрицы симплекс&кода. Позднее, в 1974 году, этот подход был обоб&

щен Беловым [16], и построен еще один класс кодов. Другой подход

был предложен в 1981 и развит в 1983 году Tor Helleseth and Henk

С.A.van Tilborg [17, 18], он заключался в новом методе комбиниро&

вания порождающих матриц симплекс&кодов и добавлении к ним

новых элементов. Более поздние работы связаны с попытками при&

менения понятий проективной геометрии в построении кодов, таких

как проективные плоскости, minihyper [19].

К сожалению, все предложенные в данных работах коды двоич&

ные, для q&ичного случая в общем виде не было предложено ни одной

конструктивной процедуры построения. Кроме того, все предложен&

ные коды строятся на базе симплекс&кодов или различными комби&

нациями кодов, поэтому все они имеют очень большие длины, а сле&

довательно, и большой размер алфавита. По этим двум причинам все

рассматриваемые ранее конструкции нам не подходят.

Мы предлагаем воспользоваться другим способом построения ко&

дов, лежащих на границе Грайсмера. Этот способ не дает возможнос&

ти гарантированного построения целого класса кодов, но позволяет

получать отдельные экземпляры кодов, лежащих на границе Грайс&

мера или очень близко к ней. Будем строить алгебро&геометрические

коды на базе несингулярных эллиптических кривых, данный способ

построения рассматривался во многих работах и гарантирует полу&

чение кодов с длинной

1nkd g1232

[29], где g – это род кривой. Так

как границу Грайсмера можно представить в следующем виде:

ndk

3 4 5 4

то нетрудно подобрать параметры кривой для построения кода, ле&

жащего на границе Грайсмера. Можно было бы говорить о построе&

нии целого класса кодов, у которых

4 5

но, к сожалению, при

выборе параметров приходится ориентироваться еще на одно огра&

ничение, существующее на коды, строимые с использованием кри&

вых

2nqg q

3 4

[29]. Данное ограничение не позволяет увеличи&

вать длину кода до бесконечности, следовательно, мы можем гово&

рить только о построении отдельных экземпляров кодов. Для нашей

схемы можно воспользоваться любым из предложенных ранее под&

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

некоторые примеры для их наглядного сравнения с уже существую&

щими схемами построения CFF.

Применения CFF

CFF может применяться в различных приложениях. Множество ра&

бот посвящено описанию взаимосвязи между различными комбинатор&

ными объектами. Данные работы предлагают, каким образом можно

построить различные комбинаторные схемы на базе CFF. Существует

также множество работ, которые предлагают использовать CFF в раз&

личных криптографических приложениях, таких как цифровая под&

пись [20], управление ключами [21, 22], Frame proof [23, 24], Broadcast

encryption [25, 26], Traitor tracing [27]. Кроме того, были также широ&

ко распространены исследования по применению CFF в построении схем

группового тестирования [4, 28]. Все множество опубликованных по

данной тематике работ показывает актуальность разработки новых

способов построения CFF. Предложенная нами схема может быть при&

менена в любой из рассмотренных ранее работ.

Литература

1. Kautz W. H., Singleton R. C. Nonrandom binary superimposed codes// IEEE

Transactions on Information Theory. 1964. N 10. P. 363–377.

2. Erdös P., Frankl P., Füredi Z. Families of finite sets in which no set is covered by

the union of r others// Israel Journal of Mathematics. 1985. N 51. P. 75–89.

3. Stinson D. R., Wei R. Combinatorial properties and constructions of traceability

schemes and frameproof codes// SIAM Journal on Discrete Mathematics. 1998.

N 11. P. 41–53.

4. Hwang K. F., Sтs V. T. Non&adaptive hypergeometric group testing// Studia

Sci. Math. Hungar. 1987. N 22. P. 257–263.

5. Wei R. On cover&free families: Preprint.

6. Garcia A., Stichtenoth H. A tower of Artin&Schreier extensions of function

fields attaining the Drinfeld&Vladut bound// Invent. Math. 1995. N 121.

P. 211–222.

7. Kumar R., Rajagopalan S., Sahai A. Coding constructions for blacklisting

problems without computational assumptions// Advances in Cryptology – Crypto ’99:

Lecture Notes in Computer Scienc. 1999. N 1666. P. 609–623.

8. Stinson D. R., van Trung Tran, Wei R. Secure frameproof codes, key distribution

patterns, group testing algorithms and related structures// Journal of Statistical

Planning and Inference. 2000. N 86. P. 595–617.

9. Staddon J. N., Stinson D. R. and Wei R. Combinatorial properties of frameproof

and traceability codes// IEEE Transactions on Information Theory. 2001. N 47.

P. 1042–1049.

10. Stinson D. R., Wei R. Generalized cover&free families: Preprint.

11. Дьячков А. Г., Рыков В. В. Границы на длину разделяющих кодов//

Проблемы передачи информации. 1982. Вып. 18. С. 7–13.

12. Füredi Z. On r&cover&free families// Journal of Combinatorial Theory. 1996.

A 73. P. 172–173.

13. Ruszinko M. On the upper bound of the size of the r&cover&free families//

Journal of Combinatorial Theory. 1994. A 66. P. 302–310.

14. MacWilliams F. J., A. Sloane N. J. The Theory of Error& Correcting Codes.

Amsterdam: North&Holland, 1977.

15. Solomon G., Stiffler J. J. Algebraically punctured cyclic codes// Inform.

Contr. Apr. 1965. Vol. 8. P. 170–179.

16. Белов В. И., Логачев В. Н., Сандимиров В. П. Построение класса линейных

двоичных кодов, достигающих границы Варшамова–Гилберта// Проблемы пе&

редачи информации. 1974. Вып. 3. С. 36–44.

17. Helleseth T., A van Tilborg H. C. A new class of codes meeting the Griesmer

bound// IEEE Trans. Inform. Theory. Sept. 1981. Vol. IT&27. P. 548–555.

18. Helleseth T. New Constructions of Codes Meeting the Griesmer Bound// IEEE

Transactions on Information Theory. May 1983. Vol. IT&29. N 3. P. 434–439.

19. Storme L. Linear codes meeting the Griesmer bound, minihypers and geometric

applications: Preprint.

20. Pieprzyk J., Wang H., Xing C. Multiple&time signature schemes secure against

adaptive chosen message attacks// 10

Workshop on Selected Areas in Cryptography:

Lecture Notes in Computer Science, 2003.

21. Chan Aldar C.F. Distributed Symmetric Key Management for Mobile Ad Hoc

Networks// IEEE INFOCOM, 2004.

22. On key storage in secure networks / M. Dyer, T. Fenner, A. Frieze et al. //

J. Cryptology. 1995. N 8. P. 189–200.

23. Stinson D. R., Wei R. Combinatorial properties and constructions of traceability

schemes and frameproof codes// SIAM Journal on Discrete Mathematics. 1998.

N 11. P. 41–53.

24. Stinson D. R., van Trung Tran, Wei R. Secure frameproof codes, key distribution

patterns, group testing algorithms and related structures// Journal of Statistical

Planning and Inference. 2000. N 86. P. 595–617.

25. Stinson D. R., Wei R. Key reassigned traceability schemes for broadcast

encryption// Selected Areas in Cryptology – SAC ’98: Lecture Notes in Computer

Science. 1999. N 1556. P. 144–156.

26. Tracing traitors / B. Chor, A. Fiat, M. Naor et al. // IEEE Transactions on

Information Theory. 2000. N 46. P. 893–910.

27. Knill E., Bruno W. J., Torney D. C. Non&adaptive group testing in the presence

of error// Discrete Appl. Math. 1998. N 88. P. 261–290.

28. Tsfasman M.A., Vlгdut S.G. Algebraic&geometric codes// Dordrecht: Kluwer,

1991.

29. Hamada N. A. Characterization of some [n; k; d; q]&codes meeting the Griesmer

bound using a minihyper in a finite projective geometry// Discrete Math. 1993.

Vol. 116. N 1&3. P. 229–268.

В. Б. Прохорова,

заместитель директора Института компьютерной безопасности

вычислительных систем и сетей СанктПетербургского

государственного университета аэрокосмического приборостроения

МОДЕЛЬ КАНАЛА ДЛЯ СЕТИ

С РАЗНОРОДНЫМИ КАНАЛАМИ

Введение

Задача внедрения энергосберегающих технологий предполагает ре&

шение ряда сопутствующих задач, в частности, обеспечения надежной

связи. Для большинства энергосистем эта задача осложняется невоз&

можностью использовать стандартные средства связи без их доработки

применительно к рассматриваемой системе. Как правило, связь в систе&

ме осуществляется по разнородным каналам с плохими эксплуатаци&

онными характеристиками. Основным средством обеспечения высокой

надежности передачи по каналам связи в настоящее время является

использование методов теории помехоустойчивого кодирования [1].

Однако большинство результатов этой теории получены в предположе&

нии независимости ошибок в каналах связи, и существующие коррек&

тирующие коды не очень эффективны для передачи в каналах с памя&

тью, каковыми являются большинство каналов энергосистем. Моди&

фикация известных кодов для использования их в разнородных кана&

лах с памятью требует создания единого описания этих каналов. Еди&

ный, с точки зрения описания, канал связи может быть создан на осно&

ве использования в качестве метода модуляции OFDM [2], а в качестве

метода кодирования – матричного кодирования.

В статье предлагается модель для описания системы разнородных

каналов при использовании OFDM, пригодная для выбора кодов,

исправляющих ошибки.

Модель канала связи, описание сигналов

Выделим основные виды помех, вносимых каналом связи при

широкополосной передаче.

Это, прежде всего, флюктуационная помеха, обладающая широ&

ким равномерным энергетическим спектром и характеризующаяся

нормальным распределением мгновенных значений, а также поме&

хи, связанные с рассеянием и многолучевым распространением.

Еще одним характерным для широкополосных систем видом помех

являются помехи от сигналов, принадлежащих другим источникам (ад&

ресам). Эти помехи возникают из&за того, что при передаче широкопо&

лосных сигналов, сигналы, принадлежащие другим источникам, созда&

ют специфические внутрисистемные помехи. Такие помехи при высо&

кой интенсивности работы источников могут иногда быть аппроксими&

рованы гауссовским шумом с ограниченным равномерным спектром и

ограниченной энергией. При небольшой интенсивности работы источ&

ников в системе такая аппроксимация оказывается недостаточно точ&

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

исследования. К вопросу о возможностях проведения такого рода ис&

следования мы вернемся в заключении.

Кроме перечисленных, укажем также сосредоточенные помехи

(ширина спектра помехи значительно меньше ширины спектра сиг&

нала) и импульсные помехи, которые могут иметь как естественное,

так и искусственное происхождение.

Все эти помехи можно, не теряя в общности, считать независимыми

и рассматривать по отдельности. В настоящем разделе будем полагать,

что вероятность одновременной работы даже двух источников незначи&

тельна, и не будем рассматривать внутрисистемные помехи. Для описа&

ния каналов связи, подверженных воздействию флюктуационных по&

мех и помех, связанных с рассеянием и многолучевостью, мы использу&

ем модель канала с релеевским коэффициентом передачи (РКП) [3, 4].

Пусть S(t) – передаваемый (элементарный) сигнал, тогда при пе&

редаче по РКП принимаемый сигнал Z(t) можно записать в виде

() cos () ();

Zt St nt1 23 4

(t) = mcosjS(t) + n

(t) ,

где j – случайный фазовый сдвиг в канале, равномерно распределен&

ный в интервале [0, 2p]; m – случайная величина, распределенная по

закону Релея, носит название коэффициента передачи канала; Z

(t)

и Z

(t) – квадратурные компоненты принятого сигнала – выходы ко&

синусоидального и синусоидального демодуляторов соответственно;

(t) и n

(t) – квадратурные компоненты белого гауссовского шума;

n(t), n

(t) и n

(t) можно считать гауссовскими процессами.

Модель РКП позволяет с высокой точностью оценивать вероятность

ошибки при передаче S(t) в случае, если m незначительно меняется на

отрезке [0, T

] в полосе DW, где T

– длительность сигнала S(t), а DW –

его полоса. Поэтому канал с рассеянием как по частоте, так и по време&

ни (а именно таким является исследуемый нами канал [4, 15]) с поло&

сой W на отрезке времени передачи T

может быть описан с помощью

набора значений

1, , 1,

;

ij t

injn

WТ

566



случайной ве&

личины m, распределенной по релеевскому закону. Такое задание кана&

ла, по сути, соответствует делению его на подканалы или передаче по

так называемой системе параллельных каналов [4]. Естественно, что

сигнал S(t), используемый при передаче по такому каналу, должен пред&

ставлять собой суперпозицию

&сигналов (

, T

– длитель&

ность широкополосного сигнала), соответствующих частотно&времен&

ной матрице (рисунок).

() (),

St S t1

где

() ()cos ();

ii ii

St t t tS3456

(1)

(1);

i1 2 1 3 451

() ( );

ttjT1231 4

(t) – закон применения амплитуды сигнала S

(t),

1 – его несущая

частота, ()

t1 – закон изменения фазы,

– значение фазы j&го (по

времени) элемента i&го сигнала, соответствующее коду сигнала

принимающее одно из двух значений. Отметим, что традиционные

широкополосные частотно& и фазоманипулированные сигналы яв&

ляются подклассами класса сигналов, задаваемых (1), и, следова&

тельно, рассматривая в дальнейшем класс сигналов (1), мы гаранти&

руем качество передачи не худшее, чем то, которое обеспечивается

частотно& и фазоманипулированными сигналами.

Использование передачи по частотным подканалам является ог&

раничением общности рассмотрения канала. Однако можно показать,

что в каналах с замираниями (для канала с некоррелированными

замираниями это доказано, например, в [6]) существует оптималь&

ное, с точки зрения достоверности передачи (при обозримой сложно&

сти реализаций), число частотных подканалов, и это обстоятельство

в сочетании с получаемым упрощением анализа канала полностью

оправдывает указанное ограничение общности рассмотрения.

Величины

для каналов с рассеянием коррелированы между со&

бой [3, 4], их корреляция задает память канала по времени и по час&

тоте. Мы будем предполагать в дальнейшем, что зависимость вели&

чин

во времени (вдоль строк матрицы

) и по частотам (вдоль

столбцов) является марковской, и строки и столбцы матрицы

независимы между собой.

Нарезанный на полосы канал с релеевским коэффициентом пере&

дачи, в котором выполняются сделанные выше предположения, мы

будем называть частотно&временным (ЧВ&каналом).

ЧВ&канал был впервые введен в работе [4], практика использова&

ния этого канала при построении систем передачи информации пока&

зала удовлетворительное совпадение его характеристик с характери&

стиками широкого класса реальных каналов связи.

Дискретные модели ЧВканала

Введем теперь дискретную модель ЧВ&канала, которая необходи&

ма для выбора метода кодирования.

Рассмотрим двоичное отображение этого канала. Обозначим через

, , ...,

11 1 все возможные состояния частотных подканалов, а че&

рез

(1/ )

P 1

– вероятность появления ошибки в состоянии

,1,,

il12

соответственно через

, , ...,

11 1

обозначим все возможные состояния

временных подканалов, а через

(1/ )

P 1

– вероятность появления ошиб&

ки в состоянии

,1,.

jl12

Кроме того, через

(/),

P 11

где

, 1, ,ii l3

(/),

P 11

где

, 1, ,

jj l3

обозначим вероятности пе&

рехода из состояния

и из состояния

соответственно.

В силу независимости строк и столбцов матрицы коэффициентов пере&

ход из состояния

не зависит от текущего состояния Ф, и наобо&

рот, переход из

не зависит от текущего состояния t. Тогда

вероятность появления ошибки в j&й момент времени на i&й частоте бу&

дет полностью определяться лишь парой состояний

Поставим в соответствие каждой паре состояний

некоторое со&

стояние

(1)

ilj

вероятность появления ошибки в котором

(1)

(1/ ).

ilj

Стремясь к простоте изложения, ограничимся случаем двоичного

отображения ЧВ&канала связи. Хорошо известно, что этот случай

представляет наибольший интерес для практики.

Двоичным частотно&временным n &каналом будем называть мно&

жество пар

,()pxx

таких, что

1xX

, где X – множество

&мерных

двоичных векторов, p(x) – вероятность появления вектора x.

Двоичным частотно&временным ()

nn1 &каналом, где ,

nn n1

будем называть

&канал,

&мерные векторы которого нарезаны

Частотновременная матрица сигнала

ээ

() ((1))

ij i i

SSjTSj T

на последовательности длины n

. Другими словами, двоичный час&

тотно&временной ()

nn1 &канал есть множество пар {y, P(y)} таких,

что

1yY

, где Y – множество ()

nn1 &матриц над полем GF(2), P(y) –

вероятность появления матрицы y.

В соответствии с моделью непрерывного ЧВ&канала, описанной

выше, значение элемента

11yYyY

определяется коэффициентом

передачи канала i&й частоте в j&й момент времени –

Задавая правило перехода из состояния

11t

il j

в состояние

22t

il j

в соответствии с выражением

22 11

21 21

(/)(/)(/),

iljilj i i jj

PC C P P1 22 3 3

(2)

значение вероятности

(1/ )

il j

будем вычислять по формуле

(1/ ) (1/ , ) (1/ ) (1/ ) .

il j i j i j

PC P P P3453 465

(3)

Таким образом, зная характеристики непрерывной модели ЧВ&

канала, из уравнений (2) и (3) легко получить параметры его двоич&

ного отображения – двоичной модели ЧВ&канала. Выбор ее парамет&

ров сводится к определению двоичного отображения непрерывного

канала, коэффициент передачи которого распределен по закону Ре&

лея. Такая задача решалась в целом ряде работ [3, 6].

Заключение

Рассмотренная модель является общей моделью двоичного ото&

бражения ЧВ&канала. Она позволяет достаточно просто описать ха&

рактер поведения дискретного ЧВ&канала. Важным достоинством

этой модели следует считать простоту моделирования на ЦВМ опи&

сываемых ею каналов.

Использование описанной модели позволяет решать задачу выбо&

ра кода для ЧВ&канала.

Литература

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.:

Мир, 1986.

2. Прокис Дж. Цифровая связь. М.: Радио и связь, 2000.

3. Кеннеди Р. Каналы связи с замираниями и рассеянием. М.: Сов.

радио, 1973.

4. Коржик В. И., Финк Л. М. Помехоустойчивое кодирование дискрет&

ных сообщений в каналах со случайной структурой. М.: Связь, 1975.

5. Блох Э. Л., Попов О. В., Турин В. Я. Модели источника ошибок в

каналах передачи цифровой информации. М.: Связь, 1971.

6. Возенкрафт Дж., Джекобс И. Теоретические основы техники связи.

М.: Мир, 1969.

П. В. Трифонов,

аспирант

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

университет

АДАПТИВНАЯ ПЕРЕДАЧА В МНОГОПОЛЬЗОВАТЕЛЬСКИХ

МНОГОЧАСТОТНЫХ СИСТЕМАХ ВЕЩАНИЯ

Введение

В настоящее время наблюдается бурное развитие систем мобиль&

ной цифровой радиосвязи. Большинство подобных систем характе&

ризуется необходимостью обеспечения высокоскоростной передачи

данных от базовой станции к пользовательским терминалам и срав&

нительно низкой скорости передачи в обратном направлении. Так

как базовые станции цифровых радиосетей в большинстве случаев

представляют собой достаточно высокопроизводительные вычисли&

тельные устройства, возникает возможность реализации адаптивных

алгоритмов, позволяющих подстроить используемую схему переда&

чи под текущее состояние радиоканала и требования пользователей,

что дает возможность существенно снизить мощность радиосигнала,

требуемую для достижения заданного качества обслуживания

пользователей.

Многоканальная система вещания

Современные цифровые радиосистемы, как правило, характери&

зуются достаточно широкой полосой сигнала. Следствием этого яв&

ляется сильная межсимвольная интерференция. Один из широко рас&

пространенных способов ее преодоления – многочастотная передача,

состоящая в том, что исходный широкополосный канал разбивается

на большое число узкополосных подканалов, свободных от межсим&

вольной интерференции. Как правило, несущие для этих подкана&

лов выбираются ортогональными, что позволяет при выполнении оп&

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

подход получил название ортогонального частотного мультиплек&

сирования (orthogonal frequency division multiplexing – OFDM) [1].

Рассмотрим систему вещания на основе OFDM. Несложно показать,

что сигнал, принятый каждым из пользователей подобной системы,

равен

() () () ()

, 1, …, , 1, …, ,

jjjj

ki ki ki

rs kKiN1 2 3 4 11