Как называется операция обратная кодированию
MT1402: Теоретические основы информатики. Имитационное моделирование
Как отмечалось при рассмотрении исходных понятий информатики, для представления дискретных сообщений используется некоторый алфавит. Однако однозначное соответствие между содержащейся в сообщении информацией и его алфавитом отсутствует.
В целом ряде практических приложений возникает необходимость перевода сообщения хода из одного алфавита к другому, причем, такое преобразование не должно приводить к потере информации.
Введем ряд с определений.
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.
Не обсуждая технических сторон передачи и хранения сообщения (т.е. того, каким образом фактически реализованы передача-прием последовательности сигналов или фиксация состояний), попробуем дать математическую постановку задачи кодирования.
смысл которого в том, что операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднее информационное содержание знака, т.е.:
Как следует из (3.1), минимально возможным значением средней длины кода будет:
Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информации на знак первичного и вторичного алфавитов.
Из (3.2) видно, что имеются два пути сокращения %%K_
В качестве меры превышения К(А,В) над %%K_
Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, %%Q(A,B) → 0%% при %%К(А,В) → K_
Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
При декодировании двоичных сообщений возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) кодовых слов (групп элементарных сигналов), соответствующих отдельным знакам первичного алфавита. При этом приемное устройство фиксирует интенсивность и длительность сигналов, а также может соотносить некоторую последовательность сигналов с эталонной (таблицей кодов). Возможны следующие особенности вторичного алфавита, используемого при кодировании:
Комбинации перечисленных особенностей определяют основу конкретного способа кодирования, однако, даже при одинаковой основе возможны различные варианты построения кодов, отличающихся своей эффективностью. Нашей ближайшей задачей будет рассмотрение различных схем кодирования для некоторых основ.
1. Первая теорема Шеннона. Основные понятия
Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе, необходимо отнести следующие:
Для представления дискретных сообщений используется некоторый алфавит. Однако однозначное соответствие между содержащейся в сообщении информацией и его алфавитом отсутствует.
В целом ряде практических приложений возникает необходимость перевода сообщения хода из одного алфавита к другому, причем, такое преобразование не должно приводить к потере информации.
Код — (1) правило, описывающее соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторичного алфавита.
(2) набор знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфавита.
Кодирование — перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.
Декодирование — операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов.
Кодер — устройство, обеспечивающее выполнение операции кодирования.
Декодер — устройство, производящее декодирование.
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.
Не обсуждая технических сторон передачи и хранения сообщения (т.е. того, каким образом фактически реализованы передача-прием последовательности сигналов или фиксация состояний), дается математическая постановка задачи кодирования.
смысл которого в том, что операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднее информационное содержание знака, т.е.:
Как следует из (3.4), минимально возможным значением средней длины кода будет:
Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информации на знак первичного и вторичного алфавитов.
Из (3.5) видно, что имеются два пути сокращения К min (А,В):
В качестве меры превышения К(А,В) над K min (А,В) можно ввести относительную избыточность кода (Q(А,В):
Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, Q(A,B) → 0 при К(А,В) → К min (А,В). Следовательно, решение проблемы оптимизации кода состоит в нахождении таких схем кодирования, которые обеспечили бы приближение средней длины кода к значению К min (А,В), равному отношению средних информации на знак первичного и вторичного алфавитов. Чем меньше Q(A,B), тем Ifin(В) ближе к Ist(A)), т.е. возникает меньше информации, связанной с кодированием, более выгодным оказывается код и более эффективной операция кодирования.
Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
и первая теорема Шеннона получает следующую интерпретацию:
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Применение формулы (3.7) для двоичных сообщений источника без памяти при кодировании знаками равной вероятности дает:
При декодировании двоичных сообщений возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) кодовых слов (групп элементарных сигналов), соответствующих отдельным знакам первичного алфавита. При этом приемное устройство фиксирует интенсивность и длительность сигналов, а также может соотносить некоторую последовательность сигналов с эталонной (таблицей кодов).
Возможны следующие особенности вторичного алфавита, используемого при кодировании:
Комбинации перечисленных особенностей определяют основу конкретного способа кодирования, однако, даже при одинаковой основе возможны различные варианты построения кодов, отличающихся своей эффективностью.
1. Первая теорема Шеннона. Основные понятия
Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе, необходимо отнести следующие:
Для представления дискретных сообщений используется некоторый алфавит. Однако однозначное соответствие между содержащейся в сообщении информацией и его алфавитом отсутствует.
В целом ряде практических приложений возникает необходимость перевода сообщения хода из одного алфавита к другому, причем, такое преобразование не должно приводить к потере информации.
Код — (1) правило, описывающее соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторичного алфавита.
(2) набор знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфавита.
Кодирование — перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.
Декодирование — операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов.
Кодер — устройство, обеспечивающее выполнение операции кодирования.
Декодер — устройство, производящее декодирование.
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.
Не обсуждая технических сторон передачи и хранения сообщения (т.е. того, каким образом фактически реализованы передача-прием последовательности сигналов или фиксация состояний), дается математическая постановка задачи кодирования.
смысл которого в том, что операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднее информационное содержание знака, т.е.:
Как следует из (3.4), минимально возможным значением средней длины кода будет:
Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информации на знак первичного и вторичного алфавитов.
Из (3.5) видно, что имеются два пути сокращения К min (А,В):
В качестве меры превышения К(А,В) над K min (А,В) можно ввести относительную избыточность кода (Q(А,В):
Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, Q(A,B) → 0 при К(А,В) → К min (А,В). Следовательно, решение проблемы оптимизации кода состоит в нахождении таких схем кодирования, которые обеспечили бы приближение средней длины кода к значению К min (А,В), равному отношению средних информации на знак первичного и вторичного алфавитов. Чем меньше Q(A,B), тем Ifin(В) ближе к Ist(A)), т.е. возникает меньше информации, связанной с кодированием, более выгодным оказывается код и более эффективной операция кодирования.
Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
и первая теорема Шеннона получает следующую интерпретацию:
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Применение формулы (3.7) для двоичных сообщений источника без памяти при кодировании знаками равной вероятности дает:
При декодировании двоичных сообщений возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) кодовых слов (групп элементарных сигналов), соответствующих отдельным знакам первичного алфавита. При этом приемное устройство фиксирует интенсивность и длительность сигналов, а также может соотносить некоторую последовательность сигналов с эталонной (таблицей кодов).
Возможны следующие особенности вторичного алфавита, используемого при кодировании:
Комбинации перечисленных особенностей определяют основу конкретного способа кодирования, однако, даже при одинаковой основе возможны различные варианты построения кодов, отличающихся своей эффективностью.
Задача кодирования
Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 25.02.2009 |
| Размер файла | 212,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Одним из средств решения подобных несоответствий в системах передачи цифровой информации, является применение помехоустойчивых кодов, лежащих в основе устройств кодирования/декодирования. Высокоэффективным средством решения данной проблемы является применение помехоустойчивого кодирования, основанного на введении искусственной избыточности в передаваемое сообщение. Помехоустойчивое кодирование передаваемой информации позволяет в приемной части системы обнаруживать и исправлять ошибки.
Актуальность: Работа подавляющего числа современных систем связи основана на передаче сообщений в цифровом виде. Сбой при приеме любого элемента цифровых данных способен вызвать значительное искажение всего сообщения в целом, что, в свою очередь, может привести к полной потере информации, содержащейся в нем. В современных информационных системах важнейшей задачей является обеспечение информационной безопасности, связанной с методами криптографии и кодирования, теоретические основы которой заложил Шеннон в своих трудах. В данной работе будут рассмотрены основы задачи кодирования, а также практическое применение помехоустойчивых кодов.
Объект: процесс формирования цифровых сигналов
Предмет: кодирование информации
Цель исследования: разработать алгоритм на основе анализа задачи кодирования.
1) Проанализировать теоретические основы задачи кодирования.
2) Рассмотреть основные виды помехоустойчивых кодов.
3) Практическая реализация помехоустойчивого кодирования.
1 1 Теоретические основы задачи кодирования
1.1 Постановка задачи кодирования
Прежде чем рассмотреть задачу кодирования, необходимо рассмотреть ряд определений, использующихся в теории кодирования [1]:
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.
Без технических сторон передачи и хранения сообщения (т.е. того, каким образом фактически реализованы передача-прием последовательности сигналов или фиксация состояний), математическая постановка задачи кодирования, дается следующим образом. [5]
смысл которого в том, что операция обратимого кодирования может увеличить количество формальной информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднюю информационную емкость знака, т.е.:
В частном случае, когда появление любых знаков вторичного алфавита равновероятно, согласно формуле Хартли I1 (B) =log2M, и тогда
По аналогии с величиной R, характеризующей избыточность языка, можно ввести относительную избыточность кода (Q):
Ранее указывалось, что источник сообщения включает кодирующую систему, формирующую сигналы по известным получателю правилам. Ввиду независимости содержания сообщения от выбранной формы его представления, возможно преобразование одного кода в другой, предоставив правило обратного преобразования получателю сообщения. Целесообразность такого дополнительного кодирования сообщения на передающей стороне и соответствующего декодирования на приемной стороне возникает из-за избыточности алфавита сообщения и искажения сигналов действующими в канале связи помехами. Кодирование предшествует хранению и передаче информации.
Основными задачами кодирования являются:
1. Обеспечение экономичности передачи информации посредством устранения избыточности.
2. Обеспечение надежности (помехоустойчивости) передачи информации
3. Согласование скорости передачи информации с пропускной способностью канала
Соответствие между элементами дискретных сообщений и видом кодирования обеспечивается выбором:
1. длительности сигналов
2. Длины кодового слова
3. Алфавита знаков и способа кодирования (побуквенного, блочного)
Различают побуквенное и блочное кодирование. При побуквенном кодировании каждому знаку внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита. [2]
При блочном кодировании слову из знаков внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита.
Cлова из знаков внутреннего алфавита В, сопоставленные словам из знаков внешнего алфавита А по правилу G, называются кодовыми комбинациями. Если ArE A и G(Ar)= Br, то говорят, что слову Ar соответствует кодовая комбинация Br. Совокупность кодовых комбинаций используемых для передач заданного количества дискретных сообщений называют кодовым словарем.
Процесс, обратный кодированию, заключается в восстановлении из кодовой комбинации Br=b1b2…bmr слова Ar=a1a2…anr из входного алфавита и называется декодированием. Если процесс кодирования осуществляется с использованием правила G, то процесс декодирования основан на применении правила G-1, где G-1 есть отображение, обратное отображению G.
Операции кодирования и декодирования называют обратимыми, если их последовательное применение обеспечивает возврат к исходной форме сообщения без потери информации.
Примером обратимого кодирования является представление знаков в телеграфном коде при передаче сообщений и восстановление их при приеме.
Примером необратимого кодирования является перевод текста с одного естественного языка на другой. (Обратный перевод побуквенно обычно не соответствует исходному тексту.)
Чтобы код был обратимым, необходимо:
1) чтобы разным символам входного алфавита А были сопоставлены разные кодовые комбинации;
2) чтобы никакая кодовая комбинация не составляла начальной части какой-нибудь другой кодовой комбинации.
Наиболее простым правилом кодирования является сопоставление каждому символу входного алфавита А слова конечной длины в выходном алфавите В. Код может быть задан в форме таблицы, графа, аналитического выражения, то есть в тех же формах, что и отображение.
Ранее отмечалось, что при передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Так, например, если вы попытаетесь передать речевое сообщению в ветреную погоду человеку, находящемуся от вас на значительном расстоянии, то оно может быть сильно искажено такой помехой как ветер. Вообще, передача сообщений при наличии помех является серьезной теоретической и практической задачей. Ее значимость возрастает в связи с повсеместным внедрением компьютерных телекоммуникаций, в которых помехи неизбежны.[1]
Например, каждый фрагмент текста («предложение») передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, большая избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Отсюда следует задача устранения избыточности, или эффективного кодирования. Впервые теоретическое исследование такого рода проблем предпринял К.Шеннон.
Первая теорема Шеннона о передаче информации, которая называется также основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:[5]
При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак кодируемого алфавита, будет сколь угодно близко к отношению средних информаций на знак первичного и вторичного алфавитов.
Используя понятие избыточности кода, можно дать более короткую формулировку теоремы:
При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
Таким образом, оптимальное кодирование принципиально возможно.
Наиболее важна для практики ситуация, когда М=2, то есть информацию кодируют лишь двумя сигналами 0 и 1. [1]
Шенноном была рассмотрена ситуация, когда при кодировании сообщения в первичном алфавите учитывается различная вероятность появления знаков, а также равная вероятность появления знаков вторичного алфавита. Тогда:
и первая теорема Шеннона получает следующую интерпретацию:
При отсутствии помех передачи средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Определение количества переданной информации при двоичном кодировании сводится к простому подсчету числа импульсов (единиц) и пауз (нулей). При этом возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) отдельных кодов. Приемное устройство фиксирует интенсивность и длительность сигналов. Элементарные сигналы (0 и 1) могут иметь одинаковые или разные длительности. Их количество в коде (длина кодовой цепочки), который ставится в соответствие знаку первичного алфавита, также может быть одинаковым (в этом случае код называется равномерным) или разным (неравномерный код). Наконец, коды могут строиться для каждого знака исходного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов). В результате при кодировании (алфавитном и словесном) возможны следующие варианты сочетаний:
Таблица 1. Варианты сочетаний
Длительности элементарных сигналов
Кодировка первичных символов (слов)
Длительность двоичного элементарного импульса показывает, сколько времени требуется для передачи 1 бит информации. Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время. Таким образом, задачу оптимизации кодирования можно сформулировать в иных терминах: построить такую систему кодирования, чтобы суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей.
Если имеется источник информации с энтропией Н(х) и канал связи с пропускной способностью С, то если С > H(X), то всегда можно закодировать достаточно длинное сообщение таким образом, что оно будет передано без задержек. Если же, напротив, С 0 значительно больше вероятности перехода 0 > 1 или наоборот. В таких каналах очень маловероятно, чтобы в одном блоке были переходы обоих видов, и поэтому почти все ошибки приводят к изменению веса блока, и, следовательно, обнаруживаются.
К комбинационным кодам можно отнести также антифединговые коды, предназначенные для обнаружения и исправления ошибок в каналах с замираниями (федингом) сигналов. Для таких каналов с группированием ошибок применяют метод перемежения символов или декорелляции ошибок. Он заключается в том, что символы, входящие в одну кодовую комбинацию, передаются не непосредственно друг за другом, а перемежаются символами других кодовых комбинаций исходного систематического или любого другого кода. Если интервал между символами, входящими в одну кодовую комбинацию, сделать длиннее «памяти» (интервала корелляции) канала с замираниями, то в пределах длительности одной исходной кодовой комбинации группирования ошибок не будет. На приёме после обратной «расфасовки» в кодовых комбинациях можно производить декодирование с обнаружением и исправлением ошибок.
В систематических кодах различают два метода формирования проверочной группы символов: поэлементный и в целом.
Наиболее известны среди систематических кодов коды Хемминга, которые исторически были найдены раньше многих других кодов и сыграли большую роль в развитии теории корректирующих кодов. В этих кодах используется принцип проверки на чётность определённого ряда информационных символов.
Проверочная группа из r символов формируется поэлементно по соответствующему алгоритму. Коды Хемминга, имеющие dmin = 3, позволяют исправить одну ошибку
Циклические коды также относятся к классу линейных систематических кодов и обладают всеми их свойствами. Коды названы циклическими потому, что циклический сдвиг любой разрешённой кодовой комбинации также является разрешённой комбинацией. Теория построения циклических кодов базируется на разделах высшей алгебры, изучающей свойства двоичных многочленов.
Особую роль в этой теории играют так называемые неприводимые многочлены, т.е. полиномы, которые не могут быть представлены в виде произведения многочленов низших степеней. В связи с этим циклические коды относят к разновидности полиномиальных кодов.
В циклических кодах » r » проверочных символов, добавляемых к исходным » k » информационным, могут быть получены сразу, т.е. в целом, в результате умножения исходной подлежащей передаче кодовой комбинации Q(x) простого кода на одночлен x r и добавлением к этому произведению остатка R(x), полученного в результате деления произведения на порождающий полином P(x).
Ошибки в передаваемых словах могут возникать вследствие либо независимых искажений разрядов (в этом случае применяют, например, коды типа кода Хэмминга), либо искажений группы рядом стоящих разрядов (для таких случаев разработаны коды, исправляющие одиночные пачки ошибок, и коды, исправляющие более одной пачки ошибок); для обнаружения ошибок в процессе вычислений на ЭВМ разработаны так называемые арифметические коды.
1.4.2 Основные параметры и построение помехоустойчивых кодов
Одним из путей решения задачи повышения верности в настоящее время является использование специальных процедур, основанных на применении помехоустойчивых (корректирующих) кодов.
Помехоустойчивыми называются коды, позволяющие обнаруживать и (или) исправлять ошибки в кодовых словах, которые возникают при передаче по каналам связи. Эти коды строятся таким образом, что для передачи сообщения используется лишь часть кодовых слов, которые отличаются друг от друга более чем в одном символе. Эти кодовые слова называются разрешенными. Все остальные кодовые слова не используются и относятся к числу запрещенных.
Применение помехоустойчивых кодов для повышения верности передачи данных связанно с решением задач кодирования и декодирования.
Основные параметры помехоустойчивых кодов
Стиранием называется «потеря» значения передаваемого символа в некоторой позиции кодового слова, которая известна.
Код, в котором каждое кодовое слово начинается с информационных символов и заканчивается проверочными символами, называется систематическим.
k—число символов в исходной комбинации
r—число контрольных символов
Декодирование кода может производиться либо в режиме обнаружения ошибки, либо в режиме исправления ошибок. Если полученная из канала кодовая комбинация является одной из разрешенных, то она считается принятой правильно, хотя на самом деле могла передаваться другая разрешенная комбинация. Если принятая комбинация не является одной из разрешенных комбинаций, то в режиме обнаружения ошибки фиксируется факт обнаружения ошибки, и кодовая комбинация, в общем случае, стирается, т.е. удаляется из дальнейшей обработки, а в режиме исправления ошибки предпринимается попытка исправить искажение (исправить ошибки).
Исправление ошибки выполняется по какому-то правилу или критерию выбора разрешенной комбинации, в которую преобразуется принятая искаженная комбинация (не равная передаваемой в канал связи). При декодировании двоичных алгебраических кодов используется принцип максимума правдоподобия, в основу которого положено предположение, что в канале связи вероятность ошибки большей кратности меньше вероятности меньшей кратности. Т. е. если в канале может исказиться один из символов кодовой комбинации (кратность ошибки t = 1 ), два символа ( t = 2), три символа (t = 3) и т.д., то справедливо для вероятностей искажения Р(t = 1) > Р(t = 2) > Р(t = 3) … Если такое предположение справедливо для используемого дискретного канала, то в декодере, который не знает, что было искажено в принятой кодовой комбинации, оправдано отождествить с передаваемой комбинацией ту из разрешенных комбинаций, которая ближе по расстоянию от комбинации, подлежащей исправлению. Самая близкая (отличающаяся в меньшем числе символов) разрешенная комбинация считается переданной и объявляется результатом исправления ошибки.
В реальном канале связи часто наблюдается группирование ошибок, когда искажается не один двоичный символ, а целый пакет, длина которого может превышать величину [(d-1)/2]. Это обстоятельство является одной из причин, ограничивающей широкое применение кодов с исправлением ошибок. Для широкого применения кодов с исправлением ошибок такой код в качестве одного из своих свойств должен обеспечивать гарантированную границу для вероятности ошибки декодирования в канале связи с произвольным распределением потока ошибок в канале связи.
В таком канале в зависимости от кратности ошибки t вероятность ошибки декодирования
1/(q-1) i-2 + 1/(q-1) i при tРС =1
При исправлении tРС ошибок в [9] предлагается оценка
То есть, если кратность ошибки t превосходит исправляющую способность кода tpc, то в канале, не являющемся q-ичным симметричным, вероятность ошибки декодирования не зависит от основания кода q при исправлении tpc ошибок и достаточно близка к единице при малых tpc. Но q-ичный симметричный канал не существует в природе, особенно для больших q, свойство равновероятности (q—1) значений искаженного q-ичного символа для такого канала достигается применением стохастического преобразования q-ичных символов канала.[3]
С учетом сказанного выше, можно сказать, что теория алгебраического кодирования с алгоритмом декодирования по принципу максимального правдоподобия для исправления независимых ошибок является примером того, как ошибочная постановка задачи о независимых ошибках в канале связи сводит практически на нет труды целого поколения исследователей.
Для обеспечения применения кодов, исправляющих ошибки, сформулируем два варианта постановки задачи. [4]
При этом будем учитывать требования к защите информации в современных информационных и телекоммуникационных системах.. Особенностями таких глобальных систем является передача очень больших массивов информации и использование различных каналов связи наиболее простым образом без проведения исследования их свойств, в том числе модели ошибок в них.