Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,441

УЛУЧШЕНИЕ ЭФФЕКТИВНОСТИ МНОГОПОРОГОВЫХ ДЕКОДЕРОВ В КАНАЛАХ СВЯЗИ СО СТИРАНИЯМИ

Золотарев В.В. 1 Овечкин Г.В. 1 Шевляков Д.А. 1
1 ФГБОУ ВПО «Рязанский государственный радиотехнический университет»
Выполнена постановка задачи повышения корректирующей способности многопороговых декодеров (МПД) в каналах связи со стираниями. Для решения поставленной задачи проведено исследование эффективности МПД, в ходе которого были построены новые более длинные и менее чувствительные к размножению ошибок самоортогональные коды. Показано, что применение новых СОК и большего количества итераций позволяет значительно уменьшить вероятность невосстановления стирания. Также была предложена новая каскадная схема, где в качестве внешнего кода использовался код с контролем по четности (ККЧ), а в качестве внутреннего – МПД. Представлен теоретический и практический результат работы каскада, позволяющий при снижении информативности передаваемых данных на 2 % (длина ККЧ равна 50 бит) при вероятности стирания 0,36 повысить корректирующую способность кодека на три десятичных порядка. Сделан вывод о целесообразности использования МПД в цифровых системах связи, в том числе использующих каналы со стираниями.
системы передачи данных
помехоустойчивое кодирование
самоортогональные коды
многопороговые декодеры
надежность передачи данных
компьютерное моделирование
каналы со стираниями
код с контролем по четности
1. Гринченко Н.Н., Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Применение многопорогового декодера в каналах со стираниями // Труды НТОРЭС им. А.С. Попова. – 2006. – С. 338–340.
2. Золотарев В.В. Теория и алгоритмы многопорогового декодирования / под ред. члена-корреспондента РАН Ю.Б. Зубарева. – 2-е изд. – М.: Горячая линия – Телеком, 2014. – 266 с.
3. Золотарев В.В., Зубарев Ю.Б., Овечкин Г.В. Обзор методов помехоустойчивого кодирования с использованием многопороговых алгоритмов // Цифровая обработка сигналов. – М., 2008. – № 1. – C. 2–11.
4. Золотарев В.В., Овечкин Г.В. Сравнение сложности реализации эффективных методов декодирования помехоустойчивых кодов // Цифровая обработка сигналов и ее применение: 6-я Межд. конф. и выст. – М., 2004. – Т. 1. – С. 220–222.
5. Золотарев В.В., Овечкин Г.В., Шевляков Д.А. Эффективность применения многопороговых декодеров в стирающих каналах связи // Математическое и программное обеспечение вычислительных систем: сборник статей / под ред. А.Н. Пылькина. – М., Горячая линия – Телеком, 2015. – С. 54–57.
6. Шевляков Д.А. Современные методы коррекции ошибок для цифровых систем передачи данных // Молодёжь, образование, наука: материалы VIII Российской ежегодной научно-практической конференции магистрантов, аспирантов и молодых ученых. – Уфа: Академия ВЭГУ, 2013. – С. 154–158.
7. Arikan E. Channel polarization: A method for constructing capacity-achiev ing codes for symmetric binary-input memoryless channels // IEEE Transactions on Information Theory. — 2009. – July. – Vol. 55, № 7. – Р. 3051–3073.
8. Berrou C., Glavieux A., Thitimajshima P. Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes // Proc. of the Intern. Conf. on Commun (Geneva, Switzerland). – May 1993. – Р. 1064–1070.
9. MacKay D., Neal R. Near Shannon limit performance of low density parity check codes // IEEE Electronics Letters. Aug. – 1996. – Р. 1645–1646.

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

На сегодняшний день в теории кодирования известен ряд методов помехоустойчивого кодирования/декодирования, различающихся корректирующей способностью, сложностью реализации и рядом других параметров [2, 7, 8, 9]. Одним из лучших по соотношению эффективности и сложности реализации является метод многопорогового декодирования (МПД) [3, 6].

Для МПД известен алгоритм работы в каналах связи со стираниями, применение которого позволяет существенно увеличить долю исправляемых ошибок (стираний) по сравнению со случаем применения демодулятора, формирующего жесткие решения относительно принятых битов (случай двоичного-симметричного канала связи). Известные результаты исследования эффективности МПД в таком канале [1] показали, что восстановить стертые символы оказывается значительно проще, чем исправлять ошибки.

Отметим, что представленные в [1] результаты теоретически могут быть улучшены как за счет использования лучших кодов, так и за счет применения более сложных каскадных схем кодирования. Например, в качестве внешнего кодека может быть использован кодек кода с контролем по четности (ККЧ), а в качестве внутреннего – кодек МПД. Перечисленные способы повышения эффективности МПД в каналах со стираниями и результаты их исследования в литературе описаны недостаточно полно. Поэтому целью данной статьи является устранение указанного недостатка.

Описание работы МПД в каналах со стираниями

В классической модели канала связи со стираниями каждый бит может быть передан правильно с вероятностью 1 – Pc или стерт с вероятностью Pc.

Работа МПД в канале со стираниями заключается в том, что сначала, как и в двоичном симметричном канале [2], вычисляется синдром:

zolotar01.wmf (1)

Здесь up – p-й элемент принятого из канала информационного вектора; vj – j-й элемент принятого из канала проверочного вектора; Θj – множество номеров информационных символов, участвующих в формировании j-го проверочного символа. Отметим, что стертые в канале информационные и проверочные символы при вычислении проверки не используются, а их число запоминается в разностном регистре.

Затем в процессе декодирования стертого информационного бита среди относящихся к нему проверок ищется проверка, содержащая только одно стирание (dj = 1). Очевидно, что это стирание будет вызвано декодируемым информационным битом, который по значению символа синдрома в соответствии с (1) может быть легко восстановлен. При этом также необходимо провести коррекцию всех проверок для восстановленного информационного бита и уменьшить на единицу число стираний в разностном регистре для этих же проверок [1].

Для используемых в МПД СОК известна нижняя оценка вероятности невосстановления символа в канале связи со стираниями при использовании ОД, которая равна [2]

zolotar02.wmf (2)

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

На рис. 1 представлены результаты эффективности декодирования МПД для блоковых СОК. Моделирование проводилось для кода длиной n = 16000 бит с кодовой скоростью R = 4/8 при 40 итерациях декодирования и различным минимальным кодовым расстоянием d. На этом рисунке сплошными линиями представлены зависимости вероятности стирания после декодирования Pн (вероятность невосстановления бита) от вероятности стирания Pс в канале связи со стираниями при различных значениях кодового расстояния d. Из рисунка видно, что при увеличении минимального кодового расстояния вероятность невосстановления стирания заметно уменьшается, но область, в которой МПД обеспечивает декодирование близкое к оптимальному (для d = 7 начиная с вероятности 0,46; для d = 9 начиная с вероятности 0,4 и т.д.), смещается в область меньшей вероятности стирания, тем самым удаляясь от пропускной способности канала. Также на данном рисунке представлена кривая «lowEst OD, d = 11», рассчитанная в соответствии с выражением (2), которая позволяет судить о том, что МПД для кода с d = 11 начиная с вероятности 0,37 вплотную приближается к эффективности ОД.

pic_36.wmf

Рис. 1. Характеристики в канале со стираниями для блоковых СОК при различным d

pic_37.wmf

Рис. 2. Характеристики современных методов помехоустойчивого кодирования/декодирования в канале со стираниями

В работе [1] были представлены результаты исследования эффективности МПД для блоковых СОК в каналах связи со стираниями, представленные на рис. 2 кривыми с пометкой «mtdBlock». Длина данных кодов не превосходит 8000 бит, а кодовая скорость R = 5/10 с различным числом минимальных кодовых расстояний d. При получении представленных зависимостей использовались 10 итераций декодирования.

Из данного рисунка видно, что полученные ранее характеристики МПД (кривые с пометкой «mtdBlock») превосходят эффективность практически реализуемого декодера Витерби (кривая «viterbi, R = 1/2, K = 7») и оказываются несколько хуже эффективности декодера турбо кода (кривая «turbo, R = 1/2»). Но при этом сложность практической реализации МПД (количество операций, требующихся для декодирования одного информационного бита) оказывается более чем на порядок меньше сложности декодера турбо кода [4].

В настоящее время результаты были значительно улучшены за счет того, что авторами данной работы были построены новые более длинные и менее чувствительные к размножению ошибок сверточные самоортогональные коды [5]. В частности, на рис. 2 кривыми с пометкой «mtdConv» представлены результаты моделирования для кодов длиной 200000 и 2500000 битов, кодовыми скоростями R = 4/8 и R = 32/40 и минимальными кодовыми расстояниями d = 21 и d = 9 с 50 и 150 итерациями декодирования МПД соответственно.

Представленная на рис. 2 кривая «mtdConv, R = 4/8» позволяет говорить, что с помощью МПД удается обеспечить декодирование, близкое к оптимальному, начиная с вероятности стирания 0,48. Отметим, что пропускная способность используемого стирающего канала равна 0,5, т.е. теоретически в таком канале можно исправлять до 50 % стираний. А кривая «mtdConv, R = 32/40» показывает, что, начиная с вероятности стирания 0,19, МПД обеспечивает декодирование, близкое к оптимальному для используемого сверточного кода. При этом пропускная способность стирающего канала составляет 0,8, т.е. теоретически можно исправлять до 20 % стираний.

Для дополнительного повышения корректирующей способности далее рассмотрим случай использования каскадирования СОК с контролем по четности (ККЧ).

Каскадирование блокового МПД и кода с контролем по четности

Несомненно, что одним из наиболее мощных подходов к повышению ЭВК является применение МПД в составе каскадных кодовых конструкций, поэтому для дополнительного выигрыша кодирования предлагается совместное использование МПД СОК и ККЧ. При использовании каскадирования в качестве внешнего кода будем использовать ККЧ с кодовой скоростью R1, а в качестве внутреннего – МПД со скоростью R2. При этом R1 должна быть как можно ближе к 1 для того, чтобы доля полезной информации (без проверочных символов) оставалась на прежнем уровне.

Для предварительной оценки эффективности предложенной каскадной схемы полезно получить нижнюю оценку невосстановления стирания после декодера ККЧ.

Обычно код с ККЧ с длиной n используется только для обнаружения ошибок, но в данном канале связи он способен исправлять одно стирание. Это возможно, когда на вход декодера ККЧ поступает последовательность, где только один символ стерт, а все остальные не стерты. При этом вероятность невосстановления стирания выражается

zolotar03.wmf (3)

где zolotar04.wmf; p – вероятность стирания; q = 1 – p – вероятность правильного приема. Так как на вход декодера ККЧ символы поступают после МПД, то вероятность стирания p в выражении (3) будет эквивалентна выражению (2).

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

zolotar05.wmf (4)

Далее рассмотрим результаты моделирования для описанного случая каскадирования МПД и ККЧ при различных d и n СОК и длине ККЧ равной 50 битам (кривые с пометкой «cascade» на рисунках 1 и 2, соответственно). Также на данных рисунках представлены кривые с пометкой «lowEst cascade», соответствующие нижним оценкам невосстановления стирания, полученные из (4) для каскада при d = 11, которые подтверждают, что МПД способен приблизиться к ним вплотную. Из сравнения рисунков видно, что каскадная схема ведет себя похожим образом при варьировании различных параметров, что и обычный МПД, но при одной и той же вероятности стирания обеспечивает лучшую вероятность исправления на несколько десятичных порядков. В частности, при снижении информативности передаваемых данных на 2 % (длина ККЧ равна 50 бит) при вероятности стирания 0,36 удается повысить корректирующую способность кодека на три десятичных порядка (кривые «d = 11» «cascade, d = 11» на рис. 1).

Выводы

Итак, в ходе данной работы было проведено исследование МПД в каналах связи со стираниями при различных его параметрах (длины кода, минимального кодового расстояния). В процессе исследования получены новые более длинные и менее чувствительные к размножению ошибок самоортогональные коды, а также проведен сравнительный анализ с ранее полученными результатами. Далее была предложена новая каскадная схема использования МПД совместно с кодом контроля по четности в каналах связи со стираниями. Приведены нижние оценки невосстановления стирания предложенной схемы. Проведено исследование характеристик каскада при варьировании параметров кодеков СОК и ККЧ.

Полученные результаты позволяют говорить о том, что МПД способен эффективно работать в каналах связи со стираниями, а при использовании каскадной схемы способен еще на несколько десятичных порядков увеличить свою корректирующую способность, оставаясь при этом таким же легко реализуемым (как программно, так и аппаратно).

Рецензенты:

Еремеев В.В., д.т.н., профессор, директор НИИ «Фотон», ФГБОУ ВПО «Рязанский государственный радиотехнический университет», г. Рязань;

Костров Б.В., д.т.н., зав. кафедрой ЭВМ, ФГБОУ ВПО «Рязанский государственный радиотехнический университет», г. Рязань.


Библиографическая ссылка

Золотарев В.В., Овечкин Г.В., Шевляков Д.А. УЛУЧШЕНИЕ ЭФФЕКТИВНОСТИ МНОГОПОРОГОВЫХ ДЕКОДЕРОВ В КАНАЛАХ СВЯЗИ СО СТИРАНИЯМИ // Фундаментальные исследования. – 2015. – № 8-3. – С. 486-490;
URL: http://www.fundamental-research.ru/ru/article/view?id=38924 (дата обращения: 15.04.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074