Загрузка...
Учебная работа. Курсовая работа: Задача кодирования
В истинное время по каналам связи передаются данные со настолько высочайшими требованиями к достоверности передаваемой инфы, что удовлетворить эти требования обычным способами — совершенствованием антенно-фидерных устройств, повышением излучаемой мощности, понижением собственного шума приемника — оказывается экономически нерентабельным либо просто неосуществимым.
Хотя имеющиеся на данный момент системы передачи данных отвечают всем главным эталонам и требованиям, они все таки не являются совершенными. обстоятельств тому воздействие помех в канале связи. При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых символов. естественный язык владеет большенный избыточностью (в европейских языках — до 7%), чем разъясняется большая помехоустойчивость сообщений, составленных из символов алфавитов таковых языков. Примером, иллюстрирующим устойчивость российского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». тут 26% знаков «поражены», но это не приводит к потере смысла. Таковым образом, в данном случае избыточность является полезным свойством. Избыточность могла бы быть применена и при передаче кодированных сообщений в технических системах. к примеру, любой фрагмент текста («предложение») передается три раза, и верным считается та пара фрагментов, которая стопроцентно совпала. Но, нездоровая избыточность приводит к огромным временным затратам при передаче инфы и просит огромного размера памяти при ее хранении. В первый раз теоретическое исследование действенного кодировки предпринял К. Шеннон.
Одним из средств решения схожих несоответствий в системах передачи цифровой инфы, является применение помехоустойчивых кодов, лежащих в базе устройств кодировки/декодирования. Высокоэффективным средством решения данной задачи является применение помехоустойчивого кодировки, основанного на внедрении искусственной избыточности в передаваемое сообщение. Помехоустойчивое кодирование передаваемой инфы дозволяет в приемной части системы обнаруживать и исправлять ошибки.
Актуальность: Работа подавляющего числа современных систем связи базирована на передаче сообщений в цифровом виде. Сбой при приеме хоть какого элемента цифровых данных способен вызвать существенное искажение всего сообщения в целом, что, в свою очередь, может привести к полной потере инфы, содержащейся в нем. В современных информационных системах важной задачей является обеспечение информационной сохранности, связанной с способами криптографии и кодировки, теоретические базы которой заложил Шеннон в собственных трудах. В данной работе будут рассмотрены базы задачки кодировки, также практическое применение помехоустойчивых кодов.
объект: процесс формирования цифровых сигналов
Предмет: кодирование инфы
Цель исследования: создать метод на базе анализа задачки кодировки.
Задачки:
1) Проанализировать теоретические базы задачки кодировки.
2) Разглядеть главные виды помехоустойчивых кодов.
3) Практическая реализация помехоустойчивого кодировки.
1
Теоретические базы задачки кодировки
1.1
Постановка задачки кодировки
До этого чем разглядеть задачку кодировки, нужно разглядеть ряд определений, использующихся в теории кодировки [1]:
Код – (1) правило, описывающее соответствие символов либо их сочетаний 1-го алфавита знакам либо их сочетаниям другого алфавита; — (2) знаки вторичного алфавита, применяемые для представления символов либо их сочетаний первичного алфавита.
Кодирование – перевод инфы, представленной средством первичного алфавита, в последовательность кодов.
Декодирование — операция, оборотная кодированию, т.е. восстановление инфы в первичном алфавите по приобретенной последовательности кодов.
Операции кодировки и декодирования именуются обратимыми, если их последовательное применение обеспечивает возврат к начальной инфы без каких-то ее утрат.
Информационная энтропия — в теории связи энтропия употребляется как мера неопределенности ожидаемого сообщения, т.е. энтропия источника инфы с независящими сообщениями есть среднее арифметическое количеств инфы сообщений
Примером обратимого кодировки является 1-го естественного языка на иной – оборотный перевод, совершенно говоря, не восстанавливает начального текста. Непременно, для практических задач, связанных со знаковым представлением инфы, возможность восстановления инфы по ее коду является нужным условием внедрения кода, потому в предстоящем изложении будет рассматриваться лишь обратимое кодировки.
Таковым образом, кодирование предшествует передаче и хранению инфы. При всем этом, как указывалось ранее, хранение соединено с фиксацией некого состояния носителя инфы, а передача – с конфигурацией состояния со временем (т.е. действием). Эти состояния либо сигналы будем именовать простыми сигналами – конкретно их совокупа и составляет вторичный алфавит.
Без технических сторон передачи и хранения сообщения (т.е. того, каким образом практически реализованы передача-прием последовательности сигналов либо фиксация состояний), математическая постановка задачки кодировки, дается последующим образом. [5]
Пусть первичный алфавит A содержит N символов со средней информацией на символ, определенной с учетом вероятностей их возникновения, I1
(A)
(нижний индекс отражает то событие, что рассматривается 1-ое приближение, а верхний индекс в скобках показывает алфавит). Вторичный алфавит B пусть содержит M символов со средней информационной емкостью I1
(A).
Пусть также начальное сообщение, представленное в первичном алфавите, содержит n символов, а закодированное сообщение – m символов. Если начальное сообщение содержит I(A)
инфы, а закодированное – I(B)
, то условие обратимости кодировки, т.е. неисчезновения инфы при кодировке, разумеется, быть может записано последующим образом:
I(A)
≤ I(B)
,
смысл которого в том, что операция обратимого кодировки может прирастить количество формальной инфы в сообщении, но не может его уменьшить. Но любая из величин в данном неравенстве быть может заменена произведением числа символов на среднюю информационную емкость знака, т.е.:
n*I1
(
A
)
≤ n*I1
(
B
)
,
либо
I1
(
A
)
≤ m/n*I1
(
B
)
Отношение m/n, разумеется, охарактеризовывает среднее число символов вторичного алфавита, которое приходится применять для кодировки 1-го знака первичного алфавита – будем именовать его длиной кода либо длиной кодовой цепочки и обозначим K(B)
(верхний индекс показывает алфавит кодов). [
В личном случае, когда возникновение всех символов вторичного алфавита равновероятно, согласно формуле Хартли I1
(B)
=log2
M, тогда и
I1
(A)
/log2
M≤ K(
B
)
(1)
По аналогии с величиной R, характеризующей избыточность языка, можно ввести относительную избыточность кода (Q):
Q= 1 – I(A)
/ I(B)
= 1- I1
(A)
/ K(B)
*I1
(B)
(2)
Данная величина указывает, как операция кодировки прирастила длину начального сообщения. Разумеется, чем меньше Q (т.е. чем поближе она к 0 либо, что то же, I(B)
поближе к I(A)
), тем наиболее прибыльным оказывается код и наиболее действенной операция кодировки. Выгодность кодировки при передаче и хранении – это экономический фактор, так как наиболее действенный код дозволяет затратить на передачу сообщения меньше энергии, также времени и, соответственно, меньше занимать линию связи; при хранении употребляется меньше площади поверхности (размера) носителя. При всем этом следует сознавать, что выгодность кода не схожа временной выгодности всей цепочки кодирование – передача – декодирование; вероятна ситуация, когда за внедрение действенного кода при передаче придется рассчитываться тем, что операции кодировки и декодирования будут занимать больше времени и других ресурсов (к примеру, места в памяти технического устройства, если эти операции выполняются с его помощью).
Ранее указывалось, что источник сообщения включает кодирующую систему, формирующую сигналы по известным получателю правилам. Ввиду независимости содержания сообщения от избранной формы его представления, может быть преобразование 1-го кода в иной, предоставив правило оборотного преобразования получателю сообщения. Необходимость такового доп кодировки сообщения на передающей стороне и соответственного декодирования на приемной стороне возникает из-за избыточности алфавита сообщения и преломления сигналов действующими в канале связи помехами. Кодирование предшествует хранению и передаче инфы.
Реализация главных черт канала связи кроме разработки технических устройств, просит решения информационных задач – выбор рационального способа кодировки.[11]
Главными задачками кодировки являются:
1. Обеспечение экономичности передачи инфы средством устранения избыточности.
2. Обеспечение надежности (помехоустойчивости) передачи инфы
3. Согласование скорости передачи инфы с пропускной способностью канала
Соответствие меж элементами дискретных сообщений и видом кодировки обеспечивается выбором:
1. продолжительности сигналов
2. Длины кодового слова
3. Алфавита символов и метода кодировки (побуквенного, блочного)
Полагается, что сообщение источника инфы формируется из символов аi, i=1,2,.. Na наружного (входного, первичного) алфавита А объемом Na. Сообщения представляют собой слова, образованные последовательностью nr символов: Ar =a1a2…anr. В кодирующем устройстве слово Ar преобразуется в кодовое слово Br=b1b2…bmr, составленное из mr символов bj
, j=1,2,..Nb внутреннего (выходного, вторичного) алфавита В. Число символов кодового алфавита именуют основанием кода. Число символов в кодовом слове именуют длиной кодового слова. Отображение G огромного количества слов в алфавите А на огромное количество слов в алфавите В именуют кодирующим отображением либо кодом. Применение кодирующего отображения G к хоть какому слову из входного алфавита именуется кодировкой. Другими словами код — это правило отображения символов 1-го алфавита в знаки другого алфавита, кодирование – это преобразование одной формы сообщения в другую средством обозначенного кода.
Различают побуквенное и блочное кодирование. При побуквенном кодировке любому знаку наружного алфавита ставиться в соответствие кодовое слово из символов внутреннего алфавита. [2]
При блочном кодировке слову из символов наружного алфавита ставиться в соответствие кодовое слово из символов внутреннего алфавита.
Cлова из символов внутреннего алфавита В, сопоставленные словам из символов наружного алфавита А по правилу G, именуются кодовыми комбинациями. Если ArE A и G(Ar)= Br, то молвят, что слову Ar соответствует кодовая композиция Br. совокупа кодовых композиций применяемых для передач данного количества дискретных сообщений именуют кодовым словарем.
процесс, оборотный кодированию, заключается в восстановлении из кодовой композиции Br=b1b2…bmr слова Ar=a1a2…anr из входного алфавита и именуется декодированием. Если процесс кодировки осуществляется с внедрением правила G, то процесс декодирования основан на применении правила G-1, где G-1 есть отображение, оборотное отображению G.
Операции кодировки и декодирования именуют обратимыми, если их последовательное применение обеспечивает возврат к начальной форме сообщения без утраты инфы.
Пусть Ar — слово в алфавите А и Br =G(Ar) — слово в алфавите В. Код именуется обратимым, если для хоть какого слова Br =G(Ar) в алфавите В существует единственное преобразование G-1(Br)= Ar . Другими словами, по слову Br в алфавите В, постоянно совершенно точно восстанавливается слово Ar в алфавите А, из которого было образовано слово Br.
Примером обратимого кодировки является представление символов в телеграфном коде при передаче сообщений и восстановление их при приеме.
Примером необратимого кодировки является перевод текста с 1-го естественного языка на иной. (Оборотный перевод побуквенно обычно не соответствует начальному тексту.)
Чтоб код был обратимым, нужно:
1) чтоб различным символам входного алфавита А были сопоставлены различные кодовые композиции;
2) чтоб никакая кодовая композиция не составляла исходной части какой-либо иной кодовой композиции.
Более обычным правилом кодировки является сравнение любому символу входного алфавита А слова конечной длины в выходном алфавите В. Код быть может задан в форме таблицы, графа, аналитического выражения, другими словами в тех же формах, что и отображение.
Выражение (1) пока следует принимать как соотношение оценочного нрава, из которого непонятно, в которой степени при кодировке может быть приближение к равенству его правой и левой частей. По данной нам причине для теории связи важное информацию. 2-ая аксиома относится к настоящим линиям связи с помехами.
1.2. 1-ая аксиома Шеннона
Ранее отмечалось, что при передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых символов. Так, к примеру, если вы попытаетесь передать речевое сообщению в ветреную погоду человеку, находящемуся от вас на значимом расстоянии, то оно быть может очень искажено таковой помехой как ветер. Совершенно, передача сообщений при наличии помех является суровой теоретической и практической задачей. Ее значимость увеличивается в связи с повсеместным внедрением компьютерных телекоммуникаций, в каких помехи неминуемы.[1]
При работе с кодированной информацией, искажаемой помехами, можно выделить последующие главные задачи: установления самого факта того, что вышло искажение инфы; выяснения того, в котором непосредственно месте передаваемого текста это вышло; исправления ошибки – хотя бы с некой степенью достоверности.
Помехи в передачи инфы — свойство никак не только лишь технических систем. Это — полностью обыденное дело в быту. Пример был выше; остальные примеры — разговор по телефону, в трубке которого «трещит», вождение кара в тумане и т.д. Почаще всего человек полностью благопристойно совладевает с каждой из обозначенных выше задач, хотя и не постоянно дает для себя отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-либо ассоциативных связей). Понятно, что естественный язык владеет большенный избыточностью (в европейских языках — до 70%), чем разъясняется большая помехоустойчивость сообщений, составленных из символов алфавитов таковых языков. Примером, иллюстрирующим устойчивость российского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». тут 26% знаков «поражены», но это не приводит к потере смысла. Таковым образом, в данном случае избыточность является полезным свойством.
К примеру, любой фрагмент текста («предложение») передается три раза, и верным считается та пара фрагментов, которая стопроцентно совпала. Но, большая избыточность приводит к огромным временным затратам при передаче инфы и просит огромного размера памяти при ее хранении. Отсюда следует задачка устранения избыточности, либо действенного кодировки. В первый раз теоретическое исследование такового рода заморочек предпринял К.Шеннон.
1-ая аксиома Шеннона о передаче инфы, которая именуется также главный аксиомой о кодировке при отсутствии помех, формулируется последующим образом:[5]
При отсутствии помех передачи постоянно вероятен таковой вариант кодировки сообщения, при котором среднее число символов кода, приходящихся на один символ кодируемого алфавита, будет сколь угодно близко к отношению средних информаций на символ первичного и вторичного алфавитов.
Используя понятие избыточности кода, можно отдать наиболее маленькую формулировку аксиомы:
При отсутствии помех передачи постоянно вероятен таковой вариант кодировки сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
Данные утверждения являются аксиомами и, как следует, должны доказываться, но подтверждения мы опустим. Для нас принципиально, что аксиома открывает принципную возможность рационального кодировки. Но нужно сознавать, что из самой аксиомы никаким образом не следует, как такое кодирование выполнить фактически – для этого должны привлекаться какие-то доп суждения, что и станет предметом следующего обсуждения.
Таковым образом, наилучшее кодирование принципно может быть.
Более принципиальна для практики ситуация, когда М=2, другими словами информацию кодируют только 2-мя сигналами 0 и 1. [1]
Шенноном была рассмотрена ситуация, когда при кодировке сообщения в первичном алфавите учитывается разная возможность возникновения символов, также равная возможность возникновения символов вторичного алфавита. Тогда:
Кmin
(А, В)= I(
A
)
/ log2
M= I(
A
)
,
тут I (A)
— средняя информация на символ первичного алфавита.
Ограничим себя ситуацией, когда M = 2, т.е. для представления кодов в полосы связи употребляется только два типа сигналов – более просто реализуемый вариант. Схожее кодирование именуется двоичным. Знаки двоичного алфавита принято обозначать «0» и «1. Удобство двоичных кодов и в том, что любой простый сигнал (0 либо 1) несет внутри себя 1 бит инфы (log2
M = 1); тогда из (1), аксиомы Шеннона:
I1
(A)
≤ K(2)
и 1-ая аксиома Шеннона получает последующую интерпретацию:
При отсутствии помех передачи средняя длина двоичного кода быть может сколь угодно близкой к средней инфы, приходящейся на символ первичного алфавита.
Определение количества переданной инфы при двоичном кодировке сводится к обычному подсчету числа импульсов (единиц) и пауз (нулей). При всем этом возникает неувязка выделения из потока сигналов (последовательности импульсов и пауз) отдельных кодов. Приемное устройство фиксирует интенсивность и продолжительность сигналов. Простые сигналы (0 и 1) могут иметь однообразные либо различные продолжительности. Их количество в коде (длина кодовой цепочки), который ставится в соответствие знаку первичного алфавита, также быть может схожим (в этом случае код именуется равномерным) либо различным (неравномерный код). В конце концов, коды могут строиться для всякого знака начального алфавита (алфавитное кодирование) либо для их композиций (кодирование блоков, слов). В итоге при кодировке (алфавитном и словесном) вероятны последующие варианты сочетаний:
Таблица 1. Варианты сочетаний
Продолжительности простых сигналов
Шифровка первичных знаков (слов)
Ситуация
однообразные
равномерная
(1)
однообразные
неравномерная
(2)
различные
равномерная
(3)
различные
неравномерная
(4)
В случае использования неравномерного кодировки либо сигналов разной продолжительности (ситуации (2), (3) и (4)) для отделения кода 1-го знака от другого меж ними нужно передавать особый сигнал – временной разделитель (признак конца знака) либо использовать такие коды, которые оказываются неповторимыми, т.е. несовпадающими с частями остальных кодов. При равномерном кодировке схожими по продолжительности сигналами (ситуация (1)) передачи специального разделителя не требуется, так как отделение 1-го кода от другого делается по общей продолжительности, которая для всех кодов оказывается схожей (либо схожему числу бит при хранении).
Продолжительность двоичного простого импульса указывает, сколько времени требуется для передачи 1 бит инфы. Разумеется, для передачи инфы, в среднем приходящейся на символ первичного алфавита, нужно время. Таковым образом, задачку оптимизации кодировки можно сконструировать в других определениях: выстроить такую систему кодировки, чтоб суммарная продолжительность кодов при передаче (либо суммарное число кодов при хранении) данного сообщения была бы меньшей.
Если имеется источник инфы с энтропией Н(х) и канал связи с пропускной способностью С, то если С > H(X), то постоянно можно закодировать довольно длинноватое сообщение таковым образом, что оно будет передано без задержек. Если же, напротив, С < H(X), то передача инфы без задержек невозможна.
1-ая аксиома Шеннона декларирует возможность сотворения системы действенного кодировки дискретных сообщений, у которой среднее количество двоичных знаков на один знак сообщения асимптотически стремится к энтропии источника сообщений (в отсутствии помех).
1-ая аксиома Шеннона (переформулировка). [13]
При отсутствии помех средняя длина двоичного кода быть может сколь угодно близкой к средней инфы, приходящейся на символ первичного алфавита.
Какие же могут быть индивидуальности вторичного алфавита при кодировке:
Простые коды 0 и 1 могут иметь однообразные продолжительности (t0=t1) либо различные (≠).
Длина кода быть может схожей для всех символов первичного алфавита (код равномерный) либо различной (неравномерный код)
Коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование) либо для их композиций (кодирование блоков, слов).
1.3 2-ая аксиома Шеннона
Отношение пропускной возможности канала связи к скорости неискаженной передачи знаков алфавита передаваемого сообщения обязано быть больше либо равно энтропии передачи 1-го знака.[5]
2-ая аксиома Шеннона говорит, что при наличии помех в канале постоянно можно отыскать такую систему кодировки, при которой сообщения будут переданы с данной достоверностью. При наличии ограничения пропускная способность канала обязана превосходить производительность источника сообщений. 2-ая аксиома Шеннона устанавливает принципы помехоустойчивого кодировки. Для дискретного канала с помехами аксиома утверждает, что, если скорость сотворения сообщений меньше либо равна пропускной возможности канала, то существует код, обеспечивающий передачу со сколь угодно малой частотой ошибок.
подтверждение аксиомы основывается на последующих рассуждениях. Сначало последовательность X={xi
} кодируется знаками из В так, что достигается наибольшая пропускная способность (канал не имеет помех). Потом в последовательность из В длины n вводится r знаков по каналу передается новенькая последовательность из n + r знаков. Число вероятных последовательностей длины n + r больше числа вероятных последовательностей длины n. Огромное количество всех последовательностей длины n + r быть может разбито на n подмножеств, любому из которых сопоставлена одна из последовательностей длины n. При наличии помехи на последовательность из n + r выводит ее из соответственного подмножества с вероятностью сколь угодно малой.[12]
Аксиома дозволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность n + r, и тем вернуть начальную последовательность длины n.
Эта аксиома не дает определенного способа построения кода, но показывает на пределы достижимого в области помехоустойчивого кодировки, провоцирует поиск новейших путей решения данной нам задачи.
1.4 Помехоустойчивые коды
1.4.1 систематизация помехоустойчивых кодов
В истинное время темпы развития телекоммуникационных систем стали предпосылкой для возникновения принципно новейших методов кодировки сообщений. При этом одной из задач кодировки сделалось не только лишь достоверная передача, да и стремительная обработка данных. Невзирая на рост мощности вычислительной техники, животрепещущим остается вопросец построения обычных алгоритмов корректировки ошибок. Одним из практически неизученных направлений в данной нам области можно считать внедрение кодов с иррациональным основанием.
Работа подавляющего числа современных систем связи базирована на передаче сообщений в цифровом виде. Сбой при приеме хоть какого элемента цифровых данных способен вызвать существенное искажение всего сообщения в целом, что, в свою очередь, может привести к полной потере инфы, содержащейся в нем. В истинное время по каналам связи передаются данные со настолько высочайшими требованиями к достоверности передаваемой инфы, что удовлетворить эти требования обычным способами — совершенствованием антенно-фидерных устройств, повышением излучаемой мощности, понижением собственного шума приемника — оказывается экономически нерентабельным либо просто неосуществимым.
Высокоэффективным средством решения данной задачи является применение помехоустойчивого кодировки, основанного на внедрении искусственной избыточности в передаваемое сообщение. Теория и техника помехоустойчивого кодировки прошли несколько шагов в собственном развитии. Вначале это было просто эмпирическое внедрение простых кодов с повторением, с неизменным весом, с одной проверкой на четность и т.д. В предстоящем теория помехоустойчивого кодировки прошла достаточно длиннющий путь развития, в процессе которого для ее сотворения использовались базы математической теории – ответвления высшей алгебры и теории чисел с приложением к настоящим системам связи.
Теория кодировки появилась в конце 40-х годов с возникновением работ Голея, Хэмминга и Шеннона. Выдающиеся два ученые Голей и Хэмминг заложили базу алгебраическим способам кодировки, которые употребляются и по сей денек, а Шеннон предложил и изучил понятие случайного кодировки. Отметим, что в современных информационных системах важной задачей является обеспечение информационной сохранности, связанной с способами криптографии и кодировки, теоретические базы которой заложил Шеннон в собственных трудах.[3]
Возникновение работ Шеннона вызвало реальную являющейся составной частью синдрома наркотического опьянения посреди ученых и инженеров, чудилось, что практическое решение этих задач будет так же просто и понятно, как Шеннон сделал это математически. Но эйфория стремительно прошла, потому что практического решения в прямой постановке Шеннона отыскать так не удалось. В то же время, изготовленные Шенноном постановки задачки и подтверждение базовых теорем теории инфы дали толчок для поиска решения задач с внедрением детерминированных (неслучайных) сигналов и алгебраических способов помехоустойчивого кодировки защиты от помех и шифрования для обеспечения секретности инфы .
В 50-е-70-е годы было создано огромное количество алгебраических кодов с исправлением ошибок, посреди которых более нужными стали коды Боуза-Чоудхури-Хоквингема (БЧХ), Рида-Соломона (РС), Рида-Малера, Адамара, Юстенсена, Гоппы, циклические коды, сверточные коды с различными методами декодирования (последовательное декодирование, метод Витерби), арифметические коды.
Но на практике применяется относительно маленькая группа алгебраических помехоустойчивых кодов: БЧХ, Рида-Соломона и сверхточные коды. Более обширно используются циклические коды с обнаружением ошибок в обычных протоколах HDLC, Х.25/2 (LAP-B, LAP-M). Коды Рида-Соломона с исправлением ошибок находят применение в каналах радиосвязи. В каналах спутниковой связи, характеризующихся независящим нравом ошибок, обширно используются сверхточные коды .
Необходимо подчеркнуть тот факт, что хотя имеющиеся на данный момент системы передачи данных отвечают всем главным эталонам и требованиям, они все таки не являются совершенными. обстоятельств тому воздействие помех в канале связи. Одним из средств решения схожих несоответствий в системах передачи цифровой инфы, является применение помехоустойчивых кодов, лежащих в базе устройств кодировки/декодирования.
Помехоустойчивое кодирование передаваемой инфы дозволяет в приемной части системы обнаруживать и исправлять ошибки. Коды, используемые при помехоустойчивом кодировке, именуются корректирующими кодами. Как правило, корректирующий код может исправлять меньше ошибок, чем обнаруживать. Число ошибок, которые корректирующий код может поправить в определенном интервале последовательности двоичных знаков, к примеру, в одной кодовой композиции, именуется исправляющей способностью кода.
Физическая среда, по которой передаются данные, не быть может полностью надёжной. Наиболее того, уровень шума бывает весьма высочайшим, к примеру, в беспроводных системах связи и телефонных системах. Ошибки при передаче — это действительность, которую нужно непременно учесть.[10]
В различных средах нрав помех различный. Ошибки могут быть одиночные, а могут возникать группами, сходу по несколько. В итоге помех могут исчезать биты либо напротив — появляться излишние.
Главный чертой интенсивности помех в канале является параметр шума — p. Это число от 0 до 1, равное вероятности инвертирования бита, при условии что, он был передан по каналу и получен на другом конце.
Последующий параметр — p2. Это возможность такого же действия, но при условии, что предшествующий бит также был инвертирован.
Этими 2-мя параметрами полностью можно ограничиться при построении теории. Но, в принципе, можно было бы учесть подобные вероятности для исчезновения бита, также применять полную информацию о пространственной корреляции ошибок, — другими словами корреляции примыкающих ошибок, разделённых одним, 2-мя либо наиболее битами.
У групповых ошибок есть свои плюсы и минусы. Плюсы заключаются в последующем. Пусть данные передаются блоками по 1000 бит, а уровень ошибки 0,001 на бит. Если ошибки изолированные и независящие, то 63% блоков будут содержать ошибки. Если же они появляются группами по 100 сходу, то ошибки будут содержать 1% блоков.
Зато, если ошибки не группируются, то в любом кадре они невелики, и есть возможность их поправить. Групповые ошибки портят кадр невозвратно. Требуется его повторная пересылка, но в неких системах это в принципе нереально, — к примеру, в телефонных системах, использующие цифровое кодирование, возникает эффект пропадания слов/слогов.
Для надёжной передачи кодов было предложено два главных способа.
1-ый — добавить в передаваемый блок данных нескольких «излишних» бит так, чтоб, анализируя приобретенный блок, можно было бы сказать, есть в переданном блоке ошибки либо нет. Это, так именуемые, коды с обнаружением ошибок.
2-ой — внести избыточность так, чтоб, анализируя приобретенные данные, можно не только лишь замечать ошибки, да и указать, где конкретно появились преломления. Это коды, исправляющие ошибки.
Под помехой понимается хоть какое действие, накладывающееся на нужный сигнал и затрудняющее его прием.
Наружные источники помех вызывают в главном импульсные помехи, а внутренние — флуктуационные. Помехи, накладываясь на видеосигнал, приводят к двум типам искажений: краевые и дробления. Краевые преломления соединены со смещением фронтального либо заднего фронта импульса. Дробление соединено с дроблением одного видеосигнала на некое количество наиболее маленьких сигналов. [4]
Помехоустойчивые коды делятся на блочные и непрерывные.
Блочными именуются коды, в каких информационный поток знаков разбивается на отрезки и любой из их преобразуется в определённую последовательность (блок) кодовых знаков. В блочных кодах кодирование при передаче (формирование проверочных частей) и декодирование при приёме (обнаружение и исправление ошибок) производятся в границах каждой кодовой композиции (блока) в отдельности по подходящим методам.
Непрерывные либо рекуррентные коды образуют последовательность знаков, не разделяемую на отдельные кодовые композиции. Кодирование и декодирование безпрерывно совершаются над последовательностью частей без деления их на блоки. Формирование проверочных знаков ведётся по рекуррентным (возвратимым) правилам, потому непрерывные коды нередко именуют рекуррентными либо цепными.
В простом цепном коде любой проверочный элемент формируется путём сложения по модулю 2 примыкающих либо отстоящих друг от друга на определённое число позиций информационных частей. В канал связи передаётся последовательность импульсов, в какой за каждым информационным следует проверочный.
К непрерывным кодам относятся и свёрточные коды, в каких любой информационный знак, поступающий на вход кодирующего устройства, вызывает возникновение на его выходе ряда проверочных частей, образованных суммированием по модулю 2 данного знака и » k-1 » прошлых информационных знаков. Рекуррентные коды разрешают исправлять групповые ошибки (» пачки «) в каналах связи.
Блочные коды делятся на равномерные и неравномерные. В равномерных кодах, в отличие от неравномерных, все кодовые композиции содержат однообразное число n — знаков (разрядов) с неизменной продолжительностью τ0 импульсов знаков кода. Равномерные коды в главном и используются в системах связи, потому что это упрощает технику передачи и приёма.
Традиционными примерами неравномерного кода являются код Морзе, обширно используемый в телеграфии, и код Хафмена, используемый для компрессии инфы (факсимильная связь, ЭВМ ).
Никаких особых мер по исправлению и обнаружению ошибок в коде Морзе не предусматривается в связи с большенный избыточностью самого передаваемого текста. В этом смысле код Морзе не относится к классу подкорректирующих кодов.
Практически все блочные корректирующие коды принадлежат к разделимым кодам, в каких кодовые композиции состоят из 2-ух частей: информационной и проверочной. Их знаки постоянно занимают одни и те же позиции, т.е. размещаются на определённых местах. Как правило, в таковых кодах, все кодовые композиции которых содержат n знаков, 1-ые k знаков являются информационными, а за ними размещаются (n — k) проверочных знаков. В согласовании с сиим разделимые коды получили условное обозначение – (n , k) — коды.
В неделимых кодах деление на информационные и проверочные знаки отсутствует. К таковым кодам относятся, а именно, коды с неизменным весом, так именуемые сбалансированные коды. к примеру, Интернациональным Консультативным Комитетом по телеграфии и телефонии (МККТТ) рекомендован для использования телеграфный код № 3 — семиразрядный код с неизменным весом, т.е. с числом единиц в каждой кодовой композиции, равным 3 (W = 3).
Периодические коды образуют более необъятную группу (n, k)- разделимых кодов. Индивидуальностью этих кодов будет то, что проверочные (корректирующие) знаки образуются при помощи линейных операций над информационными. Не считая того, неважно какая разрешённая кодовая композиция быть может получена в итоге линейной операции над набором к линейно независящих кодовых композиций. А именно, суммирование по модулю 2 2-ух и наиболее разрешённых композиций также дает разрешённую кодовую комбинацию.
Так как теоретической основой получения таковых композиций является математический аппарат линейной алгебры, то коды и именуют линейными, а беря во внимание, что проверочные знаки формируются по определённой системе (правилам), блочные равномерные разделимые линейные коды получили заглавие периодических. Внедрение аппарата линейной алгебры, в какой принципиальное
Эти коды получили наибольшее применение в системах передачи дискретной инфы.
Несистематические (нелинейные) коды обозначенными выше качествами не владеют и используются существенно пореже в особых вариантах. Примером нелинейного кода является уже упоминавшийся неделимый, сбалансированный код. Эти коды обычно употребляются в несимметричных каналах связи, в каких возможность перехода 1 → 0 существенно больше вероятности перехода 0 → 1 либо напротив. В таковых каналах весьма маловероятно, чтоб в одном блоке были переходы обоих видов, и потому практически все ошибки приводят к изменению веса блока, и, как следует, обнаруживаются.
Остальным примером несистематического кода является код с контрольным суммированием — итеративный код. В этом коде проверочные разряды формируются в итоге суммирования значений разрядов как в данной кодовой композиции, так и одноимённых разрядов в ряде примыкающих с ней композиций, образующих кооперативный блок. Итеративные коды разрешают получить так именуемые массивные коды, т.е. коды с длинноватыми блоками и огромным кодовым расстоянием при сравнимо обычной процедуре декодирования. Итеративные коды могут строиться как комбинационные средством произведения 2-ух либо наиболее периодических кодов.
К комбинационным кодам можно отнести также антифединговые коды, созданные для обнаружения и исправления ошибок в каналах с замираниями (федингом) сигналов. Для таковых каналов с группированием ошибок используют способ перемежения знаков либо декорелляции ошибок. Он состоит в том, что знаки, входящие в одну кодовую комбинацию, передаются не конкретно друг за другом, а перемежаются знаками остальных кодовых композиций начального периодического либо хоть какого другого кода. Если интервал меж знаками, входящими в одну кодовую комбинацию, создать длиннее «памяти» (интервала корелляции) канала с замираниями, то в границах продолжительности одной начальной кодовой композиции группирования ошибок не будет. На приёме опосля оборотной «расфасовки» в кодовых композициях можно создавать декодирование с обнаружением и исправлением ошибок.
В периодических кодах различают два способа формирования проверочной группы знаков: поэлементный и в целом.
Более известны посреди периодических кодов коды Хемминга, которые исторически были найдены ранее почти всех остальных кодов и сыграли огромную роль в развитии теории подкорректирующих кодов. В этих кодах употребляется принцип проверки на чётность определённого ряда информационных знаков.
Проверочная группа из r знаков формируется поэлементно по соответственному методу. Коды Хемминга, имеющие dmin = 3, разрешают поправить одну ошибку
Циклические коды также относятся к классу линейных периодических кодов и владеют всеми их качествами. Коды названы повторяющимися поэтому, что повторяющийся сдвиг хоть какой разрешённой кодовой композиции также является разрешённой композицией. Теория построения повторяющихся кодов базируется на разделах высшей алгебры, изучающей характеристики двоичных многочленов.
Необыкновенную роль в данной нам теории играют так именуемые неприводимые многочлены, т.е. полиномы, которые не могут быть представлены в виде произведения многочленов низших степеней. В связи с сиим циклические коды относят к разновидности полиномиальных кодов.
Посреди повторяющихся кодов особенное пространство занимает класс кодов, предложенных Боузом и Рой-Чоудхури и независимо от их Хоквингемом . Коды Боуза-Чоудхури-Хоквингема получили сокращённое наименование БЧХ — коды и различаются особым выбором порождающего (образующего) повторяющийся код полинома, что приводит к обычной процедуре декодирования.[7]
В повторяющихся кодах » r » проверочных знаков, добавляемых к начальным » k » информационным, могут быть получены сходу, т.е. в целом, в итоге умножения начальной подлежащей передаче кодовой композиции Q(x) обычного кода на одночлен x r и добавлением к этому произведению остатка R(x), приобретенного в итоге деления произведения на порождающий полином P(x).
В процессе кодировки при передаче инфы из информационных разрядов в согласовании с определёнными для всякого К. правилами формируются доп знаки — проверочные разряды. При декодировании из принятых кодовых слов по этим же правилам вновь сформировывают проверочные разряды и ассоциируют их с принятыми; если они не совпадают, означает при передаче произошла ошибка. Есть коды, обнаруживающие факт преломления сообщения, и коды, исправляющие ошибки, т. е. такие, при помощи которых можно вернуть первичную информацию.
Ошибки в передаваемых словах могут возникать вследствие или независящих искажений разрядов (в этом случае используют, к примеру, коды типа кода Хэмминга), или искажений группы стоящих разрядов (для таковых случаев разработаны коды, исправляющие одиночные пачки ошибок, и коды, исправляющие наиболее одной пачки ошибок); для обнаружения ошибок в процессе вычислений на ЭВМ разработаны так именуемые арифметические коды.
1.4.2 Главные характеристики и построение помехоустойчивых кодов
неувязка увеличения верности обоснована не соответствием меж требованиями, предъявляемыми при передаче данных и качеством настоящих каналов связи. В сетях передачи данных требуется обеспечить верность не ужаснее 10-6 — 10-9, а при использовании настоящих каналов связи и обычного (первичного) кода обозначенная верность не превосходит 10-2 — 10-5.
Одним из путей решения задачки увеличения верности в истинное время является внедрение особых процедур, основанных на применении помехоустойчивых (подкорректирующих) кодов.
Обыкновенные коды характеризуются тем, что для передачи инфы употребляются все кодовые слова (композиции), количество которых равно N=qn (q — основание кода, а n — длина кода). В общем случае они могут различаться друг от друга одним эмблемой (элементом). Потому даже один неверно принятый знак приводит к подмене 1-го кодового слова иным и, как следует, к неверному приему сообщения в целом.
Помехоустойчивыми именуются коды, дозволяющие обнаруживать и (либо) исправлять ошибки в кодовых словах, которые появляются при передаче по каналам связи. Эти коды строятся таковым образом, что для передачи сообщения употребляется только часть кодовых слов, которые различаются друг от друга наиболее чем в одном знаке. Эти кодовые слова именуются разрешенными. Все другие кодовые слова не употребляются и относятся к числу нелегальных.
Применение помехоустойчивых кодов для увеличения верности передачи данных связанно с решением задач кодировки и декодирования.
задачка кодировки заключается в получении при передаче для каждой k — элементной композиции из огромного количества qk соответственного ей кодового слова длиною n из огромного количества qn.
Задачка декодирования состоит в получении k — элементной композиции из принятого n — разрядного кодового слова при одновременном обнаружении либо исправлении ошибок. [6]
Главные характеристики помехоустойчивых кодов
Длина кода — n;
Длина информационной последовательности — k;
Длина проверочной последовательности — r=n-k;
Кодовое расстояние кода — d0;
Скорость кода — R=k/n;
Избыточность кода — Rв;
Возможность обнаружения ошибки (преломления) — РОО;
Возможность не обнаружения ошибки (преломления) — РНО.
Кодовое расстояние меж 2-мя кодовыми словами (расстояние Хэмминга) — это число позиций, в каких они различаются друг от друга.
Кодовое расстояние кода — это меньшее расстояние Хэмминга меж разными парами кодовых слов.
Стиранием именуется «утрата» значения передаваемого знака в некой позиции кодового слова, которая известна.
Код, в каком каждое кодовое слово начинается с информационных знаков и завершается проверочными знаками, именуется периодическим.
Построение помехоустойчивых кодов в главном соединено с добавлением к начальной композиции (k-символов) контрольных (r-символов) Закодированная композиция будет составлять n-символов. Эти коды нередко именуют (n,k) — коды.
k—число знаков в начальной композиции
r—число контрольных знаков
Разглядим главные понятия помехоустойчивого кодировки. Двоичный (n,k)-код подразумевает правило перехода от композиции из k информационных знаков, общее число которых 2k, к такому же числу кодовых композиций длиной n (при этом n > k), общее число которых 2n , т.е. к введению избыточности (для периодических кодов лишних знаков). Для кода существует огромное количество из 2k разрешенных кодовых композиций длиной n, любая из которых соответствует одной из информационных композиций. Если сопоставить пару кодовых композиций длиной n знаков, то число двоичных знаков в каких они не совпадают, именуют расстоянием. Если попарно сопоставить все кодовые композиции, малое из приобретенных расстояний именуют кодовым расстоянием d, которое обрисовывает способность кода исправлять либо обнаруживать преломления в канале кодовых композиций.
Декодирование кода может выполняться или в режиме обнаружения ошибки, или в режиме исправления ошибок. Если приобретенная из канала кодовая композиция является одной из разрешенных, то она считается принятой верно, хотя по сути могла передаваться иная разрешенная композиция. Если принятая композиция не является одной из разрешенных композиций, то в режиме обнаружения ошибки фиксируется факт обнаружения ошибки, и кодовая композиция, в общем случае, стирается, т.е. удаляется из предстоящей обработки, а в режиме исправления ошибки предпринимается попытка поправить искажение (поправить ошибки).
Исправление ошибки производится по какому-то правилу либо аспекту выбора разрешенной композиции, в которую преобразуется принятая искаженная композиция (не равная передаваемой в канал связи). При декодировании двоичных алгебраических кодов употребляется принцип максимума правдоподобия, в базу которого положено предположение, что в канале связи возможность ошибки большей кратности меньше вероятности наименьшей кратности. Т. е. если в канале может исказиться один из знаков кодовой композиции (кратность ошибки t = 1 ), два знака ( t = 2), три знака (t = 3) и т.д., то справедливо для вероятностей преломления Р(t = 1) > Р(t = 2) > Р(t = 3) … Если такое предположение справедливо для применяемого дискретного канала, то в декодере, который не понимает, что было искажено в принятой кодовой композиции, оправдано отождествить с передаваемой композицией ту из разрешенных композиций, которая поближе по расстоянию от композиции, подлежащей исправлению. Самая близкая (отличающаяся в наименьшем числе знаков) разрешенная композиция считается переданной и объявляется результатом исправления ошибки.
При декодировании по принципу максимума правдоподобия справедливо утверждение, что код с кодовым расстоянием d верно исправляет число ошибок t =[(d-1)/2], где [a] – наименьшее целое от а. В то же время ясно, что если реальное число искаженных знаков в кодовом блоке превосходит величину [(d-1)/2], то произойдет неправильное исправление ошибки (ошибка декодирования с вероятностью Рош ). Таковым образом, код верно исправляет ошибки с кратностью не выше [(d-1)/2], при всем этом число искаженных знаков в принимаемой информационной последовательности миниатюризируется, и заносит ошибки декодирования в итоге исправления ошибок с кратностью, превосходящей величину [(d-1)/2], когда число искажений в информационной последовательности возрастает (остаются преломления, приобретенные в канале связи, и добавляется неправильное исправление в декодере). Понятно, что если в канале связи число ошибок в кодовой последовательности может превосходить величину [(d-1)/2] с довольно большенный вероятностью, то реализация режима исправления ошибок быть может никчемной либо даже вредной.
В настоящем канале связи нередко наблюдается группирование ошибок, когда искажается не один двоичный знак, а целый пакет, длина которого может превосходить величину [(d-1)/2]. Это событие является одной из обстоятельств, ограничивающей обширное применение кодов с исправлением ошибок. Для широкого внедрения кодов с исправлением ошибок таковой код в качестве 1-го из собственных параметров должен обеспечивать гарантированную границу для вероятности ошибки декодирования в канале связи с произвольным распределением потока ошибок в канале связи.
Обычно оценка вероятности ошибки декодирования делается для q-ичного симметричного канала при вероятности преломления q-ичного знака Pq
. В таком канале с вероятностыо 1 — Pq
q-ичный знак принимается правильно, опосля его преломления с вероятностью Рq
каждое
Pq
/(q-1).
В таком канале зависимо от кратности ошибки t возможность ошибки декодирования
Pош
(t)=0 при t ≤ (dРС
-1)/2 =tРС
Pош
(t) ≤ (q-1) → ∑ Cn
S
(q-1)S
при d — tРС
≤ t≤ d-1
Pош
(t) ≤ (q-1) → ∑ Cn
S
(q-1)S
при t ≥d(1)
В канале, не являющемся q-ичным симметричным для кода РС, получены последующие оценки для t>d — tP
c
1/(q-1)i-2
+ 1/(q-1)i
при tРС
=1
P (t) ≤ (2)
1/(q-1)i-2t
-1/t! приtРС
≥ 2
При исправлении tРС
ошибок в [9] предлагается оценка
(3)
Другими словами, если кратность ошибки t превосходит исправляющую способность кода tpc, то в канале, не являющемся q-ичным симметричным, возможность ошибки декодирования не зависит от основания кода q при исправлении tpc ошибок и довольно близка к единице при малых tpc. Но q-ичный симметричный канал не существует в природе, в особенности для огромных q, свойство равновероятности (q—1) значений искаженного q-ичного знака для такового канала достигается применением стохастического преобразования q-ичных знаков канала.[3]
защита от ошибок в разных телекоммуникационных системах сводится к применению протоколов, содержащих описание 2-ух главных функций: помехоустойчивого кодировки и управления передачей на определенном протокольном уровне (для канального, сетевого и сеансового уровней) эталонной модели взаимодействия открытых систем (ЭМВОС). защита инфы в таковых системах сводится не только лишь к борьбе с независящими искажениями в канале связи (в двоичном – симметричном канале ДСК), да и к защите от группирующихся искажений (пакетов ошибок) и от намеренных искажений. Выше было показано, что в канале с наиболее сложным распределением потока ошибок, чем в ДСК, применение кодов, исправляющих ошибки, затруднено. Применение кодов с исправлением ошибок намеренного нрава до крайнего времени числилось в принципе неосуществимым, хотя бы для традиционных алгебраических кодов.
С учетом произнесенного выше, можно сказать, что теория алгебраического кодировки с методом декодирования по принципу наибольшего правдоподобия для исправления независящих ошибок является примером того, как неверная постановка задачки о независящих ошибках в канале связи сводит фактически на нет труды целого поколения исследователей.
Для обеспечения внедрения кодов, исправляющих ошибки, сформулируем два варианта постановки задачки. [4]
При всем этом будем учесть требования к защите инфы в современных информационных и телекоммуникационных системах.. Чертами таковых глобальных систем является передача весьма огромных массивов инфы и внедрение разных каналов связи более обычным образом без проведения исследования их параметров, в том числе модели ошибок в их.
1-ая постановка, являющаяся «мягенькой», заключается в том, что используемые коды с исправлением ошибок должны обеспечивать в канале с естественными помехами (ошибками) подвергаемую количественной оценке возможность ошибки декодирования раздельно по последующим соответствующим интервалам кратности ошибки:
— кратность ошибки t меньше половины величины кодового расстояния d, т.е. t £ [(d-1)/2]
— кратность ошибки t меньше величины кодового расстояния d, т.е. t < d
— кратность ошибки t больше величины кодового расстояния d, t > d³
2-ая постановка, являющаяся мощной, заключается в том, что используемые коды с исправлением ошибок должны обеспечивать в канале с произвольным нравом ошибок гарантированную верхнюю границу для вероятности ошибки декодирование на всем интервале вероятной кратности ошибки t £ n; при этом эта граница обязана устанавливаться при проектировании выбором характеристик кода.
Из эвристических суждений сформулируем характеристики помехоустойчивого кода с исправлением ошибок, которые дозволили бы обеспечить его применение для защиты инфы в современных информационных и телекоммуникационных системах в всех из имеющихся задачках внедрения.[14]
1. Код имеет режимы обнаружения и исправления ошибок с обеспечением в обоих режимах гарантированной (наперед данной) вероятности декодирования с ошибкой в случайном канале связи и надежным отказом от декодирования при невозможности исправления ошибки.
2. Код имеет такую исправляющую способность и дозволяет избрать такие характеристики n и k, что использующий их метод передачи инфы характеризуется нехудшими вероятностно-временными чертами по сопоставлению с применением других кодов.
3. Код обеспечивает в режиме исправления ошибок выделение с данной точностью части верно принятых знаков даже при кратности ошибки, превосходящей исправляющую способность кода.
4. Код дозволяет декодировать несколько копий (схожих по содержанию инфы кодовых блоков) блока с эффективностью, превосходящей эффективность декодирования начального кода с обнаружением либо исправлением ошибок. Это свойство может применяться для работы по параллельным каналам, при неоднократной передаче сообщения по одному каналу либо в канале с оборотной связью при обработке копий опосля приема повторенного блока.
5. Процедуры кодировки и декодирования кода содержат, в главном, операции по модулю 2.
6. способ кодировки должен владеть качествами случайности сигналов на выходе кодера, обеспечивающими совместное решение задач обеспечения помехоустойчивости и секретности в постановке К. Шеннона.
1.4.3 Код Шеннона
Хорошим кодом можно найти тот, в каком любой двоичный знак будет передавать наивысшую информацию. В силу формул Хартли и Шеннона максимум энтропии достигается при равновероятных событиях, как следует, двоичный код будет хорошим, если в закодированном сообщении знаки 0 и 1 будут встречаться идиентично нередко.[8]
Разглядим в качестве примера наилучшее двоичное кодирование букв российского алфавита совместно с эмблемой пробела «-». Полагаем, что известны вероятности возникновения в сообщении знаков российского алфавита, к примеру, приведенные в таблице 3.
Таблица 3.Частота букв российского языка (предположение)
К. Шеннон и Р. Фано независимо предложили в 1948-1949 гг. метод построения кода, основанный на выполнении условия равной вероятности знаков 0 и 1 в закодированном сообщении. [10]
Все кодируемые знаки (буковкы) делятся на две группы так, что сумма вероятностей знаков в первой группе равна сумме вероятностей знаков 2-ой группы (другими словами возможность того, что в сообщении повстречается знак из первой группы, равна вероятности того, что в сообщении повстречается знак из 2-ой группы).
Для знаков первой группы
Дальше любая группа делится на две подгруппы, так чтоб суммы вероятностей символов в каждой подгруппе были равны. Для знаков первой подгруппы каждой группы процесс разбиения знаков на группы и кодировки длится до того времени, пока в подгруппах не остается по одному символу.
Пример кодировки знаков российского алфавита приведен в табл. 4
Таблица 4. Пример кодировки букв российского алфавита при помощи кода Шеннна-Фано.
анализ приведенных в таблице кодов приводит к выводу, что нередко встречающиеся знаки кодируются наиболее маленькими двоичными последовательностями, а изредка встречающиеся — наиболее длинноватыми. Означает, в среднем для кодировки сообщения определенной длины будет нужно наименьшее число двоичных знаков 0 и 1, чем при любом другом методе кодировки.
совместно с тем процедура построения кода Шеннона-Фано удовлетворяет аспекту различимости Фано. Код является префиксным и не просит специального знака, отделяющего буковкы друг от друга для конкретного него декодирование двоичного сообщения.
Таковым образом, неувязка помехоустойчивого кодировки представляет собой необъятную область теоретических и прикладных исследовательских работ. Главными задачками при всем этом являются последующие: отыскание кодов, отлично исправляющих ошибки требуемого вида; нахождение способов кодировки и декодирования и обычных методов их реализации.
Более разработаны эти задачки применительно к периодическим кодам. Такие коды удачно используются в вычислительной технике, разных автоматических цифровых устройствах и цифровых системах передачи инфы.
2.Практическая реализация задачки кодировки
2.1 Пример к первой аксиоме Шеннона
задачка действенного кодировки описывается триадой:
X = {X 4i 0} — кодирующее устройство — В.
тут Х, В — соответственно входной и выходной алфавит. Под обилием х 4i 0 можно осознавать любые знаки (буковкы, слова, предложения). В — огромное количество, число частей которого в случае кодировки символов числами определяется основанием системы счисления 2 ( к примеру 2, m = 2 2) . Кодирующее устройство сопоставляет любому сообщению x 4i 0 из Х кодовую комбинацию, составленную из n 4i знаков огромного количества В. Ограничением данной задачки является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой композиции.
Для решения данной задачки обязана быть известна возможность P 4i возникновения сообщения x 4i 0, которому соответствует определенное количество знаков n 4i алфавита B. Тогда математическое ожидание количества знаков из B обусловится последующим образом: n 4ср = n 4i P 4i (средняя величина).
Этому среднему количеству знаков алфавита В соответствует наибольшая энтропия H 4max = n 4ср log m. Для обеспечения передачи инфы, содержащейся в сообщениях Х кодовыми комбинациями из В, обязано производиться условие H 4max >= H(x) 4, либо n 4ср log m >= — P 4i log P 4i . В этом случае закодированное сообщение имеет избыточность
n 4ср >= H(x)/logm, n 4min= H(x)/log 4 m.
Коэффициент избыточности
Ku = (H 4max — H(x))/H 4max = (n 4ср- n 4min )/n 4ср .
Составим подобающую таблицу. Имеем:
n 4min= H(x)/log 2 = 2.85, Ku = (2.92 — 2.85)/2.92 = 0.024,
т.е. код фактически избыточности не имеет. Видно, что среднее количество двоичных знаков стремится к энтропии источника сообщений.
Таблица 2.1 Пример к первой аксиоме Шеннона
N
0,1
P(x,4i)
(x,4i)
код
n,4i
n,4i p,4i
Px 4i log Px 4i
1
2
3
4
5
6
7
8
0.19
0.16
0.16
0.15
0.12
0.11
0.09
0.02
X1
X2
X3
X4
X5
X5
X7
X8
10
001
011
100
101
111
1011
1001
2
3
3
3
3
3
4
4
0.38
0.48
0.48
0.45
0.36
0.33
0.36
0.08
-4.5522
-4.2301
-4.2301
-4.1054
-3.6706
-3.5028
-3.1265
-3.1288
Px 41 0=1,0
=2.92
H(x)=2.85
2.2 Пример построения кода Шеннона
В таблице 2.2 приведены промежные вычисления и итог построения кода Шеннона. Средняя длина кодовых слов l = 2,95. В данном случае избыточность кода Шеннона на 0,5 бита больше, чем избыточность кода Хаффмена. Из этого рисунка понятно, почему код неэффективен. Кодовые слова для букв b , d , e , f могут быть укорочены на 1 бит без утраты характеристики конкретной декодируемости.
Таблица 2.2 Построение кода Шеннона
Буковка
Возможность p m
Кумулятивная возможность q m
Длина кодо- вого слова l m
Двоичная запись [ q]2
Кодовое слово c m
a
0,35
0,00
2
0,00…
00
b
0,20
0,35
3
0,0101…
010
c
0,15
0,55
3
0,10001…
100
d
0,10
0,70
4
0,10110…
1011
e
0,10
0,80
4
0,11001…
1100
f
0,10
0,90
4
0,11100…
1110
Докажем конкретную декодируемость кода Шеннона. Для этого выберем сообщения с номерами i и j , i < j . Кодовое слово ci
для i заранее короче, чем слово cj
для j , потому довольно обосновать, что эти слова различаются в одном из первых li
знаков.
Разглядим разность qj
− qi
=Σ pk
− Σ pk
=Σ pk
≥ pi
Вспомним, что длина слова и его возможность соединены соотношением
li
= [− log pi
]≥ − log pi
.
Потому pi
≥2-
li
.
С учетом этого неравенства
q j
− q i
≥ 2-
li
В двоичной записи числа в правой части мы имеем опосля запятой li
−1 нулей и единицу в позиции с номером li. Это значит, что по наименьшей мере в одном из li
разрядов слова ci
и cj
различаются и, как следует, ci
не является префиксом для cj
. Так как это правильно для хоть какой пары слов, то код является префиксным.
Заметим, что длины кодовых слов в коде Шеннона буквально такие же, какие были выбраны при подтверждении прямой аксиомы кодировки. Повторяя выкладки, получим уже известную оценку для средней длины кодовых слов
l ≤ H +1.
Броско, что при построении кода Шеннона мы избрали длины кодовых слов примерно равными (чуток большенными) своей инфы соответственных сообщений. В итоге средняя длина кодовых слов оказалось примерно равной (чуток большей) энтропии ансамбля.
2.3 Пример Кода Шеннона
Допустим, необходимо закодировать некое сообщение: AABCDAABC
Имеем :
A — 5 5/10 = 0.5
B — 2 2/10 = 0.2
C — 2 2/10 = 0.2
D — 1 1/10 = 0.1
Длина всего сообщения 10 (Рассчитывается веpоятность встpечаемости всякого знака и pасполагаем их в столбик в поpядке yбывания веpоятностей)
Опосля этого стpоим кодовые композиции пpостым способом. Делим столбик с веpоятностями таковым обpазмо, чтоб сyмма веpоятностей веpхней части pавнялась пpиблизительно сyмме веpоятностей нижней части
0.5 — пеpвая часть = 0.5
——
0.2
0.2 | — втоpая часть = 0.5
0.1 /
Напpитив веpоятностей веpхней части пpоставляем нyли, напpотив нижней — еденицы. В нашем пpимеpе полyчим.
0.5 0
0.2 1
0.2 1
0.1 1
Пpделываем позже то же с pазделенными частями. В конце-концов пpидем к томy, что разделять больше нечего.
А 0.5 0
B 0.2 10
C 0.2 110
D 0.1 111
Итого — AABCDAABC = 0 0 10 110 111 0 0 10 110
Пpичем закодиpованное сообщение (это видно) не быть может pаскодиpовано несколькими методами, хотя длина кодов знаков различается. Чтоб пpочитать закодиpованное сообщение стpоится бинаpное деpево. В нашем слyчае оно бyдет такое.
()
/
0(A) 1
/
0(B) 1
/
0(C) 1(D)
Вот еще пpимеp составления кодовых композиций по веpоятносям:
0.3 00
0.25 01
————— (пеpвое деление)
0.1 100
0.1 101
————- (втоpое деление)
0.1 1100
0.05 1101
———— (тpетье деление)
0.05 1110
0.05 1111
2.4 Пример кодировки и декодирования способом Шеннона-Фано
При помощи табл. 4 можно закодировать и декодировать хоть какое сообщение. В виде примера запишем двоичным кодом фразу: «Теория информаций»
0 111 010000 11 01 000 11 011 11 0000
01101000111111 111 00110 100
11 0000 10111111 10101100110
Отметим, что тут нет необходимости отделять буковкы друг от друга особым знаком, т.к. и без этого декодирование производится совершенно точно. Убедимся в этом, декодируя при помощи табл. 4 последующую фразу:
10011100110011001001111010000
1011100111001001101010000110101
010110000110110110
Итог декодирования — фраза «метод кодировки». При таком кодировке неважно какая ошибка (случайное перепутывание символов 0 и 1) гибельна, т.к. декодирование всего последующего за ошибкой текста становится неосуществимым. Потому данный принцип кодировки употребляется тогда, когда ошибки при кодировке и передаче сообщения исключены.
Заключение
В процессе курсовой работы была рассмотрена задачка кодировки, которая содержит в себе:
1.Обеспечение экономичности передачи инфы средством устранения избыточности.
2. Обеспечение надежности (помехоустойчивости) передачи инфы
3.Согласование скорости передачи инфы с пропускной способностью канала
задачка кодировки является одним из основных понятий информатики, потому что кодирование предшествует передаче и хранению инфы, и, соответственно, является основой их удачного воплощения.
При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых символов. Эта неувязка решается при помощи помехоустойчивого кодировки. Помехоустойчивое кодирование передаваемой инфы дозволяет в приемной части системы обнаруживать и исправлять ошибки. Коды, используемые при помехоустойчивом кодировке, именуются корректирующими кодами. В первый раз, исследование действенного кодировки произвел Клод Шеннон. Для теории связи важное
В работе были рассмотрены эти аксиомы, и можно придти к выводу, что 1-ая – затрагивает ситуацию с кодировкой при передаче сообщения по полосы связи, в какой отсутствуют помехи, искажающие информацию, т.е. эта аксиома является образцом, какими должны быть помехоустойчивые коды, 2-ая аксиома относится к настоящим линиям связи с помехами.
В процессе курсовой работы были составлены примеры кодировки, на базе первой аксиомы Шеннона. Это кодировки является довольно действенным, потому что получаемый код фактически не имеет избыточности, но, к огорчению, в настоящих линиях связи огромное количество помех, и таковой итог недостижим. Потому код Шеннона не является таковым же действенным как, к примеру код Хафмена. Но, невзирая на это необходимо отметить, что Клод Шеннон был одним из основоположников теории кодировки и его работы занесли большой вклад в развитие информатики.
]]>