Содержание к диссертации
Введение
Глава 1. Потенциальные корректирующие свойства недвоичных МПП-кодов 11
1.1. Введение 11
1.2. Структура МПП-кодов над полем GF(q) 11
1.3. Нижняя оценка минимального кодового расстояния для МПП-кодов над полем GF(q) 13
1.4. Верхняя оценка минимального кодового расстояния для МПП-кодов над полем GF(q) 22
1.5. Анализ результатов 26
1.6. Выводы к главе 29
Глава 2. Реализуемые корректирующие свойства недвоичных МПП-кодов 33
2.1. Введение 33
2.2. Асимптотическая оценка доли ошибок, исправимых МПП-кода ми над полем GF(q) 33
2.3. Результаты имитационного моделирования 54
2.4. Выводы к главе 88
Глава 3. Применение недвоичных МПП-кодов в сигнально-кодо вой конструкции для системы множественного доступа 89
3.1. Введение
3.2. Описание сигнально-кодовой конструкции для векторного дизъюнктивного канала 89
3.3. Асимптотическая оценка относительной суммарной скорости передачи 93
3.4. Модифицированный вариант сигнально-кодовой конструкции для векторного канала с АБГШ 100
3.5. Результаты имитационного моделирования 103
3.6. Выводы к главе 106
Заключение 107
Литература
- Нижняя оценка минимального кодового расстояния для МПП-кодов над полем GF(q)
- Анализ результатов
- Результаты имитационного моделирования
- Модифицированный вариант сигнально-кодовой конструкции для векторного канала с АБГШ
Введение к работе
Актуальность темы. В настоящее время активное развитие вычислительной техники и информационных технологий привело к резкому увеличению объемов обрабатываемой и передаваемой информации, вследствие этого возрастают и требования к скорости передачи. В связи с этим важнейшей задачей является обеспечение высокого качества передаваемой информации (т.е. уменьшение вероятности ошибки) при высокоскоростной передаче.
Для исправления ошибок используют помехоустойчивые коды. Важнейшим обстоятельством при выборе той или иной кодовой конструкции на практике является наличие быстрых алгоритмов кодирования и декодирования. Двоичные коды с малой плотностью проверок (МПП-коды) удовлетворяют этому требованию. Однако не менее важно, чтобы алгоритмы декодирования были способны исправить большое число ошибок. Таким образом, главным вопросом является вопрос о том, насколько ухудшаются корректирующие свойства кодов при использовании простых алгоритмов декодирования. Исследованию двоичных МПП-кодов посвящено множество работ, среди которых следует особо отметить работы таких русских и зарубежных ученых, как Р. Дж. Галлагер, М. С. Пинскер, В. В. Зяблов, К. Ш. Зигангиров, А. М. Барг, Р. Таннер, Д. Спилман, Д. Маккей, Т. Ричардсон, Р. Урбанке, Д. Бурштейн, С. Л. Литсын, Ж. Земор. Доказано существование двоичных МПП-кодов, способных исправить линейно растущее с длиной кода число ошибок при сложности декодирования 0(п log2 п), где п - длина кода. Как результат, в настоящее время эти коды используются в стандартах подвижной беспроводной связи (например, LTE), цифровой телефонии; рекомендованы для использования в стандартах оптической связи, спутниковой связи, WiMAX, 802.1 In.
Все исследования будем проводить для радиочастотного канала; пусть весь диапазон частот разбит на непересекающиеся частотные поддиапазоны (подканалы) при помощи технологии мультиплексирования с использованием ортогональных частот (OFDM). В связи с ограниченностью частотного ресурса дальнейшее увеличение скорости передачи возможно лишь с помощью увеличения скорости передачи в подканалах. Этого можно добиться, увеличив мощность алфавита модуляции. Из-за этого особенно интересными становятся недвоичные корректирующие коды. Недвоичные МПП-коды впервые рассмотрены в работе М. Дэви и Д. Маккея. Число работ, посвященных исследованию недвоичных МПП-кодов, сравнительно невелико. В существующих работах по этой теме приводятся результаты имитационного моделирования. Однако результатов исследований методом имитационного моделирования недостаточно.
Таким образом, необходимо исследовать корректирующие свойства недвоичных МПП-кодов теоретически и методом имитационного моделирования,
а также рассмотреть возможность применения этих кодов в современных системах связи. Так как в настоящее время пристальное внимание уделяется построению систем множественного доступа, то, в первую очередь, необходимо рассмотреть возможность применения недвоичных МПП-кодов в системах множественного доступа.
Цель диссертационной работы: исследовать корректирующие свойства недвоичных МПП-кодов теоретически и методом имитационного моделирования, а также разработать сигнально-кодовую конструкцию (СКК) на основе недвоичных МПП-кодов для системы множественного доступа.
Для достижения поставленных целей необходимо решить следующие задачи:
о Исследовать потенциальные корректирующие свойства МПП-кодов над полем GF{q).
о Исследовать реализуемые корректирующие свойства МПП-кодов над полем GF(q) теоретически и методом имитационного моделирования.
о Разработать СКК на основе недвоичных МПП-кодов для системы множественного доступа. Провести исследование полученной системы в канале с аддитивным белым гауссовским шумом методом имитационного моделирования.
Научная новизна. В настоящей работе впервые:
о Теоретически исследованы потенциальные и реализуемые корректирующие свойства МПП-кодов над полем GF(q).
о Предложен алгоритм декодирования МПП-кодов над полем GF(q) с вводом стираний.
о МПП-коды над полем GF(q) использованы в СКК для системы множественного доступа.
Теоретическая и практическая ценность. Получены верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF(q). Улучшена асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем GF(q) с помощью алгоритма, имеющего сложность 0{п log2n). Получена нижняя оценка относительной суммарной скорости передачи для системы множественного доступа, использующей бесшумный векторный дизъюнктивный канал. Эта оценка асимптотически совпадает с верхней оценкой.
Результаты, полученные в процессе подготовки диссертационной работы, использованы в программе фундаментальных исследований Президиума РАН «Проблемы создания национальной научной распределенной информационно-вычислительной среды на основе GRID технологий и современных телекоммуникационных сетей» по направлению «Распределенная обработка данных. Информационная безопасность сетевых технологий» (№ Госрегистрации 01200965142), программе фундаментальных научных исследований ОНИТ РАН «Архитектура, системные решения, программное обеспечение стандартизация и информационная безопасность информационно-вычислительных комплексов новых поколений» по направлению № 3.1 «Обеспечение информационной безопасности распределенных информационно-вычислительных систем» (Регистрация РАН № 10002-251/ОИТВС-04/103-96/260503-208) и разработках ЗАО «Телум», что подтверждено соответствующими актами.
На защиту выносятся следующие положения:
Верхняя и нижняя границы минимального кодового расстояния для МПП-кодов над полем GF(q).
Асимптотическая оценка доли ошибок, гарантированно исправимых МПП-кодами над полем GF(q) с помощью алгоритма декодирования, имеющего сложность 0{пlog2n).
СКК для системы множественного доступа, использующей бесшумный векторный дизъюнктивный канал, нижняя оценка относительной суммарной скорости передачи, которая асимптотически совпадает с верхней.
СКК на основе недвоичных МПП-кодов для системы множественного доступа, использующей векторный канал с аддитивным белым гауссов-ским шумом, которая позволяет одновременно работать большому числу пользователей.
Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: IEEE International Symposium on Information Theory (2011); XII International Symposium on Problems of Redundancy in Information and Control Systems (2009); XII International Workshop on Algebraic and Combinatorial Coding Theory (2010); конференциях молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (2009-2011). Кроме того, основные результаты докладывались на семинарах по теории кодирования в ИППИ РАН.
Публикации. Материалы диссертации опубликованы в 10 печатных работах, из них 4 статьи [1-4] в рецензируемых журналах и 6 статей [5-10] в сборниках трудов конференций.
Личный вклад автора Все основные научные положения и выводы, составляющие содержание диссертации, разработаны автором самостоятельно. Теоретические и практические исследования, а также вытекающие из них выводы и рекомендации проведены и получены автором лично.
Структура и объем диссертации Диссертация состоит из введения, обзора литературы, трех глав, заключения и библиографии. Общий объем диссертации 117 страниц, включая 64 рисунка и 8 таблиц. Библиография включает 83 наименования на 10 страницах.
Нижняя оценка минимального кодового расстояния для МПП-кодов над полем GF(q)
Так как д0 (5 о) это это производящая функция весов кодовых слов По кода-компонента, то д0 (s, по) = 1 + Yl a(i)s\ причем i=d0 (1.4) а(г) 0\/г Є [d0,n0] a(do) О Вычислим производную выражения, которое нужно максимизировать, получим 1 sg0{s,n0) 6 = щ д0 {s, по) Таким образом, s = f"1 (6), где / (s) = ffi, если функция J"1 (5) существует. Лемма 1.3. Функция /_1 (), где / (s) = (sn) ; существует и непрерывна на интервале (0,1). Доказательство. Для доказательства этого факта достаточно показать, что / (s) строго монотонна на [0, +оо). Вычислим производную / (s) 1 ((зд оУ до (g 0f п0 & f (s) Теперь докажем, что (sg 0) до — s (д 0) 0. Преобразуем это выражение к виду s(sg o) go-(sg Qf = По по n EwW i=d0 i+X ( v i=d0 га(г )i=d0 ґ _ . По Рассмотрим последовательности х = iy/a(i)sl и у {s/Щ n0 (это можно сделать в соответствии с условиями (1.4) и тем i=dQ фактом, что 5 0). Определим скалярное произведение (х, у) так: п0 (х,у) = 2 Х i=d0 тогда справедливо неравенство Коши-Буняковского: "п0 п0 п0 Е )2J=d0 ы2.i=do J=do Подставив наши последовательности, получим По Ew!«w ( .i=d0 По Е«« i=dn Щ i=do о, следовательно, в связи с условиями (1.4) По Е (о2» (о« i=c?o По 1 + ]Га(г)5 гг0 53 ш (г) s{ i=dQ о, что и завершает доказательство леммы. А Следствие 1.1. Исследуемая функция G{5) = {t-l)Hq(8) + + і (flog, (Г1 (6)) - -log, (50 (J"1 W ,no))J , непрерывна на (0,1) ввиду того, что J"1 ( 5) непрерывна и /_1 (5) 0 при 5 0.
Лемма 1.4. Если существует хотя бы один положительный корень (относительно переменной 5) уравнения G(6) = 0, (1.5) d0 2 и -т т, то /L( 5o-)nJ \ & ( -"G(?)J = о. где (5о - это наименьший положительный корень уравнения (1.5), є - сколь угодно малая положительная величина. Доказательство. Выберем сколь угодно малую величину є и рассмотрим следующие два предела: /V«j \ \и/=і / /L( o-e)nJ \ Шп Г« (1.7) у \W=e n\ J Сначала рассмотрим предел (1.6): Введем функцию G ( 5): с? (5) = ( -1) я?и + + і (flog, (бі") - і-log, ( (5 ,тю)) J Она получается из функции G (S) заменой s иа S1 . Очевидно, что G (5) G (5), следовательно, [є п\ _e nj lim У q-nG ) lim V q nG ) — OG L— Ъ— OQ W=\ W=l В соответствии с условиями (1.4) функция go(s,no) имеет следующий вид: 9о (s, п0) = 1 + a{d0)sd + .... Заметим, что logg [9о \5 ,щ)) -— (до (S k.noj - 1J . После преобразований получим следующую оценку для функции G (5) G(8) G {6) = -[t-l-j\8 log, 6 + О (5) Так как , dQ 2, то G ( 5) -ciSlogq 5 + с26 + о (5), С! О, [e nj /"J lim У q nG ) lim V g "1 " w=i l - (є )Сі g C2 Заметим, что знак c2 не важен, так как всегда можно сделать получившееся значение сколь угодно малым, правильно подобрав є , поэтому можно записать /Vnj lim У g-"G(") I = 0. \W=1 Теперь рассмотрим предел (1.7). Функция G (6) непрерывна на отрезке [є , 5Q — є], следовательно, существует min G (5) — Go- Go О, так как G(6) 0 при 5 Є [є : до — є] б[є ,60-є] (это следует из того, что G (5) 0 при 5 Є (0,є;) и того факта, что 5о -наименьший положительный корень). Следовательно, l(50-e)n\ _(50-c)nJ 0 lim У q-nG(%) Mm V q nG = 6- оо z— 6-s-oo— W=\e n\ W=\e n] = lim U[(60 - ) п\ - \є п\ + 1) q-nGo) = 0 6-5-00 Таким образом, 1(60-є)п\ ш[ ,--(-) 1=0. 6—?-оо \W=e n Так как оба предела существуют и конечны, то [{60-є)п\ lim У TnG(f)=0 1.4. Верхняя оценка минимального кодового расстояния для МПП-кодов над полем GF(q) Лемма 1.5. Пусть проверочная матрица Н кода С имеет специальный вид, показанный на рис. 1.3, тогда R{C) Д(Сі)(1 - т) + R{C2)T, (1.8) н тп щ н, А н2 Ч п Рис. 1.3. Специальный вид проверочной матрицы где коды С\ и С-2 соответствуют проверочным матрицам Hj и Н2 Доказательство. Пусть с Є С, тогда с имеет следующий вид с= Cci c2j. Заметим, что с і - это кодовое слово С\, его можно выбрать Сі = qRi(l)n способами. Чтобы по известному сі найти С2, нужно решить систему линейных уравнений Н24 = Ac f. У этой системы не более чем \С-2.\ = qRn решений. Таким образом, Прологарифмировав и разделив на п придем к нужному результату. Теперь, пользуясь структурой первого слоя и леммой 1.5, докажем следующую теорему н = тп ! н„ 0 -. нп 0 нп 1 Но ж" Слои 2...І - І-Ї "- ,, С Рис. 1.4. Проверочная матрица МПП-кода, приведенная к специальному виду Теорема 1.3. Пусть С Є {Ъ) и пусть d(C) = d: тогда 1т ЩО) min t + т-І ;i- R (rn,d)T) 1.9) где R irn.d) - любая верхняя граница скорости линейного кода, т = k-, У є N. Доказательство.
Приведем проверочную матрицу Н МПП-кода С к виду показанному на рис. 1.4, это можно сделать применив к столбцам матрицы перестановку 7rf . Воспользуемся леммой 1.5, получим R(C) RO(1) + R(C2)T. Код Сг соответствует подкоду С кода С. Действительно, нужно лишь добавить префикс ЙЗ (1 — т)п нулей к слову С кода С 2, чтобы получить слово с кода С, т.е. с = (0с2). Таблица 1.1 Результаты для q = R 1/8 1/4 3/8 1/2 5/8 3/4 7/8 5VG 0,7400 0,5893 0,4608 0,3462 0,2427 0,1492 0,0665 тїп {54,5р1,5ье} 0;8582 0,7382 0,6151 0,4921 0,3690 0,2460 0,1230 1 = 2 LDPC 0:7626 0,5879 0,4449 0,3260 0,2254 0,1394 0,0650 5LDPC .nO 0,6905; 64 0,4395; 64 0,2441; 64 0,1176; 64 0,0473; 64 0,0138; 64 0,0015; 64 е = з LDPC 0,8060 0,6521 0,5144 0,3906 0,2788 0,1772 0,0847 SLDPC,nO 0,7353; 48 0,5729; 64 0,4120; 48 0,2702; 48 0,1590; 64 0,0679; 48 0,0133; 48 1 = 4 x(») LDPC 0,8212 0,6764 0,5425 0,4182 0,3026 0,1948 0,0942 (0 0,7353; 32 0,5862; 48 0,4538; 64 0,3273; 64 0,2116; 64 0,1112; 64 0,0325; 64 = 8 rf(n) РС 0,8386 0,7061 0,5782 0,4547 0,3353 0,2198 0,1081 x(0 0,7353; 64 0,5862; 32 0,4582; 64 0,3445; 48 0,2412; 64 0,1462; 64 0,0571; 64 Таблица 1.2 Результаты для q = 2 R 1/8 1/4 3/8 1/2 5/8 3/4 7/8 $VG 0,7806 0,6317 0,5003 0,3804 0,2699 0,1683 0,0764 mm {64, dpi, 5be} 0,8715 0,7470 0,6225 0,4980 0,3734 0,2489 0,1244 f. = 2 LDPC 0,7738 0,5969 0,4520 0,3314 0,2294 0,1420 0,0662 dLDPC nO 0,6953; 256 0,4049; 256 0,2022; 256 0,0882; 240 0,0329; 208 0,0095: 208 0,0015: 240 1 = 3 LDPC 0,8190 0,6628 0,5232 0,3975 0,2839 0,1806 0,0864 t LDPC "0 0,7779; 144 0,5967; 240 0,4204; 240 0,2694; 240 0,1529; 256 0,0692; 240 0,0184: 144 1 = 4 LDPC 0,8351 0,6881 0,5521 0,4258 0,3083 0,1986 0,0960 dLDPC nQ 0,7794; 32 0,6300; 160 0,4856; 256 0,3471; 256 0,2226; 224 0,1205; 256 0,0418: 256 d = 8 LDPC 0,8542 0,7194 0,5893 0,4635 0,3419 0,2242 0,1103 i-(0 dLDPC nO 0,7794; 64 0,6310; 32 0,4995; 64 0,3800; 48 0,2694; 128 0,1678; 192 0,0732: 256 1.5. Анализ результатов В качестве компонентного кода будем использовать укороченный код Рида-Соломона длины щ q. Опишем, как его построить. Пусть а - это примитивный элемент поля GF(q). Рассмотрим проверочную матрицу удлиненного (q, q — do + 1) кода Рида-Соломона
Анализ результатов
Приведем описание итеративного алгоритма декодирования с жестким решением. Алгоритм srf Инициализация. Вычислить обобщенный синдром принятого вектора. Итерация цикла. Проходим по всем символам из вектора г (г), где г (0) - это принятый вектор, и для каждого из них выполняем следующее: Вычисляем решения. Рассматриваются синдромы кодов-компонентов, в которые входит данный символ. Если синдром кода-компонента ненулевой, т. е. этот код-компонент обнаружил ошибку, то вычисляем решение. Решением назовем значение, которое нужно добавить к данному символу, чтобы синдром кода-компонента стал нулевым. Кодам-компонентам с нулевыми синдромами соответствуют нулевые решения.
Критерий замены. Выбирается подмножество одинаковых ненулевых решений максимальной мощности (если таких подмножеств несколько, то выбирается любое из них). Если больше числа нулевых решений, то к символу добавляется значение решения, синдром пересчитывается. Переходим к следующему символу.
Критерий выхода из цикла. Если вес синдрома равен нулю, то выдается исправленный вектор. Иначе сравниваются веса синдрома до PI после итерации. Если вес уменьшился, то переходим к следующей итерации, иначе - отказ от декодирования.
Замечание 2.5. После каждой замены символа вес обобщенного синдрома уменьшается, так как количество синдромов кодов-компонентов, ставших нулевыми ( ), больше количества синдромов кодов-компонентов, ставших ненулевыми (их число совпадает с числом нулевых решений). Замечание 2.6. Отметим, что в случае do 2 решения существуют не всегда. Замечание 2.7. Важно отметить, что алгоритм srf работает с символами последовательно, т.е. синдром пересчитывается после каждой замены символа. Это понадобится нам в дальнейшем при доказательстве корректности алгоритма.
Теорема 2.5. Если существует по крайней мере один положительный корень (относительно переменной и) уравнения (2.1), do 2 и 4, то в ансамбле о(Ь) МПП-кодов существуют коды (с вероятностью Нт р& = 1), Ь- оо которые могут исправить любую комбинацию ошибок веса не более _ pj ПРИ сложности декодирования 0(nlog2n), причем где UJQ - наименьший положительный корень уравнения (2.1), si - сколь угодно малая положительная величина, h{u) + и log2 (q-1)- F2(a, и, щ) = О, (2.1) где h(uj) — — tulog2uj — (1 — o;)log2(l — ш) - двоичная энтропия, а функция 1 2(а, и, no) определяется следующим образом: F2(a, и.по) = h (ш) + cu logo (q — 1) /і (aamo) + n0 + max \ ш log2 (s) log2 (gQ (s, щ)) s Q [ По - — fefeS)} (2-2) где о; I + 2 2 _ сколь угодно малая положительная величина. Поиск максимума ведется по всем положительным s таким, что ашщ дг (s, щ) 1 - аищ д0 (s, щ) где до (s, по) - производящая функция весов кодовых слов компонентного кода, д\ (s, щ) - производящая функция весов всех остальных слов. Замечание 2.8. Отметим, что до (s, п0) + д\ (s, п0) = (1 + (q - 1) s) , так как (1 + (q — 1) s)n = () (д — 1) sw - производящая функция ве w=o сов всех возможных слов.
Доказательство можно разделить на три части. Сначала будет показано, что почти все коды из ансамбля (Ь) являются "хорошими", т.е. для каждого из этих кодов верно следующее утверждение: если вес комбинации ошибок W Wa, то вес обобщенного синдрома больше aWi . Далее будет доказано, что если а \ и начальная кратность ошибок не превосходит , то алгоритм srf исправит все ошибки. И, наконец, в третьей части доказательства будет показано, что алгоритм & исправит все ошибки за 0(nlog2n) операций. Существование "хороших" МПП-кодов
Пусть на элементах ансамбля (Ъ) задано равномерное распределение вероятностей. Лемма 2.6. При Ъ — со для любой фиксированной комбинации из W ошибок вероятность того, что вес обобщенного синдрома кода из ансамбля (о(Ь) не превысит величины aW, ограничена сверху величиной 2-n(F(a,oj,n0)-o(l)). iV(S aW) 2 п а - \ и = —. п Доказательство. Рассмотрим l-тый слой. Введем следующую производящую функцию: ъ QU ) = EPHN=j) (2-4) где Pw(S = j) обозначает вероятность того, что при заданном W число кодов в слое L обнаруживших ошибку, в точности равно j.
Для того, чтобы вычислить Рцг (\Si\ — j), поступим следующим образом: зафиксируем отображение (fi , а перестановки и умножения на константы будем производить с элементами вектора, а не со столбцами проверочной матрицы. Очевидно, что данные задачи эквивалентны, и так как от выбранного отображения (pi ничего не зависит, пусть оно будет тождественным. р ,ч л (1У,щ,Ь)0 где Nj (W,riQ,b) - число векторов ошибок веса W, при которых синдром 1-го Й, слоя выглядит следующим ооразом
Результаты имитационного моделирования
Алгоритм с вводом стираний предложен в работе [11]. Он был разработан для применения в случае наличия ошибок и стираний в слове на входе декодера. Однако в работе [11] показано, что он эффективнее мажоритарного алгоритма в случае, если во входном слове присутствуют только ошибки. Главное отличие этого алгоритма от мажоритарного состоит во вводе стираний на места символов, подозрительных на ошибки. На каждой итерации подозрительные символы заменяются стираниями, и далее в пределах этой итерации выполняется только исправление стираний. Стирания, которые были введены и не были исправлены, после итерации удаляются. Эти две операции повторяются до тех пор, пока не случится такого, что в процессе итерации не было исправлено ни одного стирания. Приведем формальное описание алгоритма:
Алгоритм «й Инициализация. Вычисляем обобщенный синдром. Если код-компонент содержит стирания, то его синдром не вычисляется и считается стертым.
Итерация цикла. Состоит из двух операций:
Ввод стираний на места символов, подозрительных на ошибки. Для каждого нестертого символа рассматриваются синдромы кодов-компонентов, в которые входит данный символ. Если синдром кода-компонента ненулевой и нестертый, то вычисляем решение. Нулевые и стертые синдромы соответствуют нулевым и стертым решениям (обозначим число нулевых решений через с, число стертых решений через е ). Выбирается подмножество одинаковых ненулевых и нестертых решений максимальной мощности а (если таких подмножеств несколько, то выбирается любое из них). Если а с + е, то на место рассматриваемого символа вводится стирание; синдромы кодов-компонентов, содержащих данный символ, помечаются как стертые; позиция символа добавляется в список стертых символов. Все сказанное проиллюстрировано на рис. 2.6.
Исправление стираний. Для каждого стертого символа рассматриваются синдромы кодов-компонентов, в которые входит данный символ. Нас интересуют только коды, содержащие ровно одно стирание. Для каждого из таких кодов исправим стирание, после чего сформируем список возможных значений символа. Выбирается наиболее часто встречающееся значение. Это Нулевые решения
Ввод стираний на места символов, подозрительных на ошибки. значение присваивается символу. Критерий выхода из цикла. Добавленные стирания удаляются. Сравниваются синдромы до и после итерации. В случае, если синдром изменился перейти к следующей итерации, иначе вычислить вес синдрома. Если вес нулевой - выдать исправленный вектор, иначе - отказ от декодирования.
Алгоритм распространения доверия(З ВР) Входные данные: Последовательность из априорных условных распределений для каждого из символов принятого слова. Под распределением случайной величины х при условии, что принята величина у, мы понимаем вектор следующего вида г(х\у) = (р(х = 0\у), р(х= 1\у) ,р (х = а\у),... ,р (х = aq 2\y)) , где у - принятое значение. Входные данные алгоритма можно представить в виде вектора г( = (г (Х1\Ш), г (х2\у2),..., г (хп\уп)) , где верхний индекс обозначает номер итерации (в данном случае индекс О, говорит о том, что это входные данные). Инициализация Введем две вспомогательные матрицы М = //(_/,&) размера х п и Т = T(jfk) размера щ х (п — к), содержащих соотвеиственно сообщения от символьных вершин к проверочным и от проверочных к символьным. На первой итерации элементы матрицы М инициализируются так VW =r{0)(xk\yk),j = h-J Итерация цикла: Каждая итерация разбивается на два этапа: Обработка сообщений в проверочных вершинах: Рассмотрим обработку сообщений в первой проверочной вершине. Эта вершина имеет степень щ, т.е. с ней соединены щ символьных вершин. От каждой символьной вершины j, соединенной с данной проверочной вершиной, в данную проверочную вершину приходит сообщение Uj с информацией о распределении для символа j. Для каждого из символов, входящих в данную вершину мы вычисляем новое распределение, используя текущие. Покажем это на примере трех символьных вершин xi, з?2 и х$. Пусть проверочная вершина, накладывает ограничение следующего вида h\Xi + К хч + hsxs = О, где hi Є GF(q),i = 1,...,3. Вычислим апостериорное распределение для х\. Для этого перепишем проверочное соотношение в виде х\ = —hl1(h2X2 + h3x-i). Таким образом, Х\ = -K{1{Z2 Z3), где Z2 = Ъ,2Х2) %ъ = Ыхг, легко видеть что распределения для Z2 и z% получаются с помощью перестановки элементов распределений, соответствующих ненулевым элементам поля, для Х2 и xs- Операция (g) - это операция вычисления q циклических сверток в конечном поле. Для остальных проверочных вершин поступаем аналогично. Записываем полученные распределения в сообщения ті для символьных вершин.
Обработка сообщений в символьных вершинах:
Для каждой символьной вершины у нас есть і сообщений т? с информацией о распределении для этого символа. Вычислим апостепиорное распределение для символов. Покажем на примере х\ где 0 - операция поэлементного умножения векторов. Сообщения для проверочных вершин А =г(0)(а:із/і)( 0 тЛ .
Условие выхода из цикла: После каждой итерации вычисляем синдром текущего слова (для этого необходимо принять жесткое решение для каждого из символов rW, т.е. выбрать символ с наибольшей вероятностью). Если синдром равен нулю, то выдать текущий вектор г . Кроме того, если счетчик числа итераций больше некоторой заранее заданной величины, а синдром так и не стал нулевым - выдать отказ от декодирования.
Модифицированный вариант сигнально-кодовой конструкции для векторного канала с АБГШ
Рассмотрим многопользовательский канал следующего типа. Предполагается, что канал состоит из q, q 2 независимых непересекающихся подканалов. Кроме того, предполагается, что несколько пользователей могут одновременно передавать информацию по этому каналу (обозначим число пользователей через S, S 2), причем в каждый момент времени каждый из пользователей выбирает один из подканалов для передачи. Выходом такого канала является список всех подканалов, в которых велась передача. Заметим, что информация о том, сколько именно пользователей ведут передачу в одном подканале на выходе канала недоступна. Кроме того, предполагается, что канал является бесшумным, иными словами единственным источником помех правильному приему информации, переданной некоторым пользователем, является активность других пользователей передающих по этому каналу. Эта модель предложена в работе [34]. В работах [3, 6, 8, 52] были получены оценки асимптотические пропускной способности такого канала.
Заметим, что такая модель канала допускает и более широкую трактовку. Так входы канала можно рассматривать как двоичные векторы длины q. Значение каждого элемента вектора, ассоциированного с некоторым пользователем, зависит от того, вел ли данный пользователь передачу в подканале в тот или иной момент времени. В этом случае выход канала можно рассматривать как поэлементную дизъюнкцию векторов на входе. Таким образом, этот канал является, по сути, дизъюнктивным векторным каналом.
Будем рассматривать описанную выше модель векторного канала, в которой S пользователей синхронно передают векторы. Ниже мы будем предполагать, что все пользователи используют один и тот же конечный алфавит - символы поля GF(q).
Передача. Каждый пользователь кодирует передаваемую информацию g-ичным (п, к, d) кодом С (все пользователи используют один и тот же код). Рассмотрим процесс передачи сообщения г -м пользователем. Пусть передается кодовое слово Q, каждому символу сі ставится в соответствие двоичный вектор длины q и веса 1, причем единица находится в позиции, соответствующей передаваемому элементу поля (мы предполагаем, что элементы вектора занумерованы элементами поля и этот порядок фиксирован и одинаков для всех пользователей). Обозначим таким образом построенную матрицу через Q. Передача происходит посимвольно. Перед передачей каждого двоичного вектора в канал выполняется случайная перестановка. Перестановки, используемые каждым из пользователей, выбираются равновероятно и независимо из всего множества возможных перестановок (при передаче каждого символа используется своя перестановка); используемые конкретным пользователем перестановки неизвестны никому кроме пары "приемник-передатчик".
Интервал времени за которое передается один вектор (а следовательно и поставленный ему в соответствие g-ичный символ) будем называть тактом. Для удобства пронумеруем такты целыми числами, присвоив такту с которого рассматриваемый пользователь начинает передачу номер 0, предшествующему такту номер —1, последующему номер 1 и так далее. Ниже мы будем предполагать, что в системе используется тактовая синхронизация, иными словами в течение каждого такта на каждый из входов канала поступает по одному двоичному вектору.
Прием. Базовая станция последовательно принимает сообщения от всех пользователей. Рассмотрим процесс приема сообщения, пришедшего от г -го пользователя. Будем полагать, что принимающая станция засинхронизирова-на с передатчиком каждого из пользователей. Это означает, что приемнику известны п столбцов, которые соответствуют кодовому слову, переданному г-м пользователем. При приеме каждого столбца выполняется перестановка, обратная той, что использовал г -ый пользователь при передаче. Таким образом, получим матрицу Y, = Q V \/ Xm , \m=l:S,m i J где Cj - это матрица, соответствующая кодовому слову, переданному г-м пользователем, а матрицы Хто,т = 1 : S, т ф г , - это результат действия остальных пользователей. Заметим здесь, что матрицы Хт могут не включать целиком кодовые слова остальных пользователей.
Рассмотрим кодовое слово ct Є С. Построим матрицу С , соответствующую Ct способом, описанным выше. Так как описанная нами система множе ственного доступа использует дизъюнктивный канал, все элементы матрицы на выходе канала, соответствующие кодовому слову, переданному рассматриваемым пользователем, будут ненулевыми. Поэтому предположение о том, что кодовое слово ct Є С было передано г-м пользователем, можно считать выполненным только в том случае если выполняется CtAYi = Ct, (3.1) где Л означает поэлементную конъюнкцию матриц. Для декодирования необходимо проверить выполнение условия (3.1) для всех кодовых слов используемого кода. В случае если список кодовых слов, которые удовлетворяют условию декодирования, состоит из одного слова, то это слово и есть слово переданное рассматриваемым пользователем (иначе говоря, кодовое слово было декодировано верно), если же список кодовых слов, которые удовлетворяют условию декодирования, состоит из нескольких слов, то в соответствии с принятым нами правилом принимается решение об отказе от декодирования (в рассматриваемом случае ошибочное декодирование невозможно).
Замечание 3.12. Заметим, что прием кодового слова от некоторого пользователя инициируется лишь в том случае, если этот пользователь действительно передавал информацию в системе. Последнее означает, что список кодовых слов, удовлетворяющих условию декодирования (3.1) обязательно содержит переданное рассматриваемым пользователем слово.
Замечание 3.13. Заметим, что наличие блоковой синхронизации между пользователями, передающими информацию, не предполагается (в этом отношении предложенная нами система похожа на систему множественного доступа, описанную в [2]), поэтому, вообще говоря, принимающая станция должна быть засинхронизирована с каждым из пользователей ведущих передачу в рассматриваемой системе, т.е. фактически каждому из них должен соответствовать отдельный приемник.
Замечание 3.14. В реальной системе для того, чтобы перестановки были известны и на приемнике и на передатчике целесообразно использовать засинхронизированные генераторы псевдослучайных чисел, которые традиционно применяются в системах связи, основанных на псевдослучайном переключении частот [82].
