Галкин В.А., Григорьев Ю.А. - Телекоммуникации и сети (1053870), страница 16
Текст из файла (страница 16)
во втором разряде реI ^зультирующей кодовой комбинации v^ как видно,произошла ошибка. Таким образом, в разрядах пеРис. 2.12. Схемаредаваемой кодовой комбинации, соответствующихдискретного каналаединичным разрядам вектора е, возникают ошибки.©722.2. Методы защиты от ошибок и сжатия данныхПри теоретических исследова1шях процесса возникновения ошибок в дискретном канале используют математические модели ошибок. Под математической моделью ошибки понимается распределение вероятностей по всем возможным векторам ошибки.
В соответствии с принятыми моделями ошибокразличают и дискретные каналы (ДК). Дискретный канал назьшается стационарным или однородным дискретным каналом без памяти, если условныевероятности того, что нау-й позиции кодовой комбинации принят символ >^, приусловии, что на /-й позиции на вход канала подан символ х., для всех позицийj одинаковы и не зависят от времени и от значений х.иу на других позицияхкодовой комбинации: р(у\х.) -piy^lx^^).В качестве примера рассмотрим одну из наиболее часто встречающихсямоделей ошибки, которая основана на следующей статистической гипотезе: вкаждом разряде вектора ошибки единица появляется с вероятностью р независимо от того, какие значения получили остальные разряды вектора ошибки.Такой стационарный ДК, в котором вероятности искажения любого символакодовой комбинации одинаковы, назьгаается симметричным каналом без памяти.Назовем величину, равную числу единиц в векторе ошибки, кратностьюошибки и обозначим символом q, В теории вероятностей доказьшается, чтовьщвинутой статистической гипотезе отвечает биномиальный закон распределения кратности ошибки.
Таким образом, для рассматриваемого примера математической моделью ошибки может служить вьфажениеР^=С1Р\\-РГ»f4Здесь Р^ - вероятность того, что при передаче по дискретному каналу в кодовой комбинации бинарного кода длины п появится ошибка кратности q.Значительно больший практический интерес представляют симметричныеканалы с памятью, в которых условные вероятности/7(>^|л:.) для каждой парыij зависят как от времени, так и от переходов, имевших место ранее.Подавляющее число реальньпс каналов связи имеет склонность к многоступенчатому группированию ошибок, в чем и вьфажается запоминание некоторого состояния канала.
При описании группирования ошибок с помощью простой цепи Маркова канал представляется набором состояний 5., которыепереходят друг в друга с вероятностью р.^ и в^ рпкаждом из которых опшбки независимы и происходят с вероятностью Р.. Простейшей моделью такого типа ошибки является модельГильберта (рис. 2.13).В состоянии s^ ошибки отсутствуют Pj = О,а в состоянии s^ опшбки появляются с вероятностью Р^ ^ 0. Если известны вероятности ^ис.
2.13. Модель Гильберта732. Основы телекоммуникацииnepexojisip^^^p^^.p^^.p^^, то статистика ошибок образует простую марковскуюцепь последовательности состояний с матрицей переходов:Чтобы вьшолнялось условие группирования ошибок в канале, переходныевероятности состояний должны бьггь значительно меньше вероятностей сохранения состояний, т. е. р , 2 « Pj,; P2i^^ Р22 • Тогда вероятности пребыванияканала в состояниях s^ и s^ соответственно будут равны:>-^"^ 21.^^"^2а вероятность ошибки символа:Р - РгРг= Рг-р^-(2-35)Математические модели ошибок должны отражать реальные процессы,происходящие в канале связи, и строиться на статистике помех.
Чем точнеематематическая модель описывает действительность, тем точнее можно получить оценки относительно спроектированного кода.Необходимо учитывать, что эффективность того или иного помехоустойчивого кода всегда зависит от вида помех, действующих в канале связи. Кодможет быть весьма эффективным (в том смысле, что число необнаруженныхошибок при его применении будет очень мало) при одной статистике помех иочень плохим - при другой. Поэтому при проектировании помехоустойчивыхкодов необходимо ориентироваться на определенный вид помех и в соответствии с этим в качестве исходной иметь определенную модель ошибок.Обнаружение ошибок. Наибольшее распространение при передаче дискретных сообщений получили блочные равномерные коды. Рассмотрим на примере этих кодов как обнаруживаются ошибки.
Помехоустойчивость блочныхкодов, как и других кодов, достигается введением избыточности в кодовыекомбинации. Коды, не обладающие избыточностью, не способны обнаруживать и тем более исправлять ошибки.В безызбыточных равномерных кодах длины к все 2* возможных кодовыхкомбинаций используются, т. е.
любой из 2* кодовой комбинации сопоставляется какой-либо символ внепшего алфавита. Такие коды получили название первичных кодов. Ошибка любой кратности в какой-либо кодовой комбинации всегдаприводит к ошибочному декодированию этой кодовой комбинации.
Нетрудновидеть, что кодовое расстояние для первичного кода равно единице, т. е. некоторые пары кодовых комбинаций первичного кода располагаются на минимальном расстоянии, отличном от нуля. Для обеспечения помехоустойчивости кодавводят дополнигельные разряды. Если, например, для кодирования всех символов внепшего алфавита достаточно иметь Л-разрядный первичный код, то742.2. Методы защиты от ошибок и сэюатия данныхДЛЯ обеспечения помехоустойчивости к разрядам первичного кода добавляется г избыточных разрядов.
При этом длина результирующей кодовой комбинаЩ1И становится равной я = А: + г.Различают избыточные блочные коды разделимые и неразделимые. В разделимых кодах роль разрядов кодовых комбинащ1Й разграничена: часть разрядов, часто совпадающая с разрядами исходного первичного кода, являютсяинформащюнными, остальные разряды играют роль проверочных разрядов. Внеразделимых кодах все разряды равноправные, и в кодовой комбинащш нельзяотделить информащюнные разряды от проверочных.В качестве примера неразделимого кода может служить код с постояннымвесом «3 из 7». Особенностью этого кода является то, что в любой его кодовойкомбинащш длины 7 имеется ровно три единшц>1. Таким образом, всего кодовых комбинащ1Й кода «3 из 7» будетС'--^=35.' (3! -4!)Обнаруживающая способность данного кода основывается на том, что любаяодиночная ошибка изменяет число единиц в кодовой комбинации.Таким образом, обнаружение ошибок помехоустойчивым кодом возможноблагодаря тому, что для передачи информации используются не все 2" w-разрядные кодовые комбинации равномерного кода, а лишь часть из них.
Для разделимых кодов эта часть составляет 2} кодовых комбинаций, получивших название разрешенных кодовых комбинаций. Оставшаяся часть 2" - 2* кодовыхкомбинаций, составляющая запрещенные кодовые комбинации, при передачеинформации не применяется. Использование при кодировании символов внешнего алфавита лишь части кодовых комбинаций позволяет разнести разрешенные кодовые комбинации в кодовом пространстве на расстояние, превьппающее единицу. Нетрудно видеть, что если расстояние с/ >1, то все одиночныеошибки будут переводить разрешенные кодовые комбинации в зайрещеюп>1е, апоявление запрещенной кодовой комбинации на приемной стороне может служить индикатором того, что произошла ошибка.При разработке реальных кодов учитывают статистику ошибок и требование верности передачи информации. Верность передачи оценивается частокак среднее число верно принятых кодовых комбинаций, приходящихся на однуошибочно принятую кодовую комбинацию, или как вероятность верного приема кодовой комбинации.
Так, при вьшолнении статистической гипотезы о том,что ошибки меньшей кратности появляются чаще ошибок большей кратности,исходя из требования верности передачи, определяют максимальную кратностьошибки, начиная с которой все ошибки меньшей кратности должен обнаруживать помехоустойчивый код. По максимальной кратности ошибки q^ выбирают такое минимальное кодовое расстояние, при котором все разрешенные кодовые комбинации при действии на них ошибок кратностью, не превьппающейq^, переходят в подмножество запрещенных кодовых комбинаций и, следовательно, могут быть обнаружены на приемной стороне системы передачи данных.752.
Основы телекоммуникацииРезультатом действия ошибки кратности q на разрешенную кодовую комбинацию является новая кодовая комбинация, удаленная от первоначальной нарасстояние q. Отсюда следует, что если кодовое расстояние d<q, то при действии ошибки кратности q на какую-либо разрешенную кодовую комбинациюпоследняя может перейти в другую, но тоже разрешенную кодовую комбинацию и такая ошибка уже не может быть обнаружена. Поэтому для обнаруже1шя всех ошибок, кратность которых не превышает q, кодовое расстояние должно быть больше q: d > q. Для обнаружения всех ошибок кратности, непревьппающей q^^ кодовое расстояние должно, по крайней мере, на единицупревьпыать максимальную кратность ошибки: d = qjr 1.Примером блочного разделимого кода служит код с проверкой на четность.Кодовая комбинация такого кода имеет вид a^a^..,aj).
Первые к разрядов являются информационными и, как правило, совпадают с разрядами исходногопервичного кода. Последний разряд является избыточным и определяется поформуле b = а^Ф а^® „. 0 а^. Из формулы видно, что значение избыточногоразряда зависит от того, четное или нечетное число единиц в кодовой комбинации: если число единиц четное, то 6 = О, в противном случае 6 = 1 .Если выбрать любую кодовую комбинацию первичного кода а^а^.,м^ и любую другую ближайшую к ней кодовую комбинацию а[а'^„м[, то, как легко установить, отличие между ними будет лишь в одном разряде, а отсюда следует,что кодовые комбинации будут различной четности.
При дополнении этих комбинаций проверочными разрядами последние не будут совпадать, ъ е, b ^ Ь\Следовательно, кодовые комбинации а^а^,„а^Ь и а\а'2„м[Ь' после дополненияразрядами ЬиЬ' будут отличаться уже в двух разрядах. Так как данный вьшодсправедлив для любых двух ближайших кодовых комбинаций исходного первичного кода, то после введения дополнительных разрядов вновь образованный код с проверкой на четность будет иметь кодовое расстояние J = 2 и обладать способностью обнаруживать все одиночные ошибки.Исправление ошибок. Помехоустойчивые коды, позволяющие не толькообнаруживать ошибки, но и исправлять их, называются корректирующимикодами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
