Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 9 лет назад пользователемКирилл Шаврин
1 Курс: Элементы компьютерной математики компьютерной математики Лектор – Склярова Елена Александровна
2 Тема: Элементы теории кодирования Виды кодирования. Криптография. Эффективное кодирование. Помехоустойчивое кодирование. Лекция 12
3 Виды кодирования Кодирование - это частный случай преобразования информации. Различают три вида кодирования: криптография (кодирование с засекречиванием информации). эффективное (оптимальное) кодирование; помехоустойчивое кодирование
4 Виды кодирования В схеме передачи сообщений представлены все виды кодирования и соответствующие им кодирующие устройства на передающей стороне (кодеры) и декодирующие устройства на приемной стороне (декодеры). Сокращения: К - криптографический; Э - эффективный; П - помехоустойчивый.
5 Криптография Засекречиванием информации люди занимались еще в глубокой древности. В средние века было принято зашифровывать научные результаты при первой публикации, с тем чтобы закрепить приоритет открытия – только посте этого считалось возможным сообщение дешифровать. Так, Г.Галилей (1564 – 1642 гг.), используя свой телескоп с 32-кратным увеличением, впервые наблюдал кольцо (кольца) Сатурна. Правда, вместо кольца он увидел своеобразные «придатки» - два спутника: «Altissimum planetam tergeminum observavi» («Высочайшую планету тройную наблюдал»).
6 Криптография Так, Г.Галилей (1564 – 1642 гг.), используя свой телескоп с 32-кратным увеличением, впервые наблюдал кольцо (кольца) Сатурна. Правда, вместо кольца он увидел своеобразные «придатки» - два спутника: «Altissimum planetam tergeminum observavi» («Высочайшую планету тройную наблюдал»). Здесь «высочайший» Сатурн – бог Времени и Судьбы. Зашифрованная опубликованная запись (анаграмма) представляла «фразу» на латинском языке: Smaismrmielmepcttaleumibuvnenugttaviras
7 Криптография Кстати, попытка расшифровки путем полного перебора вариантов столкнулась бы с такой оценкой количества перестановок с повторениями 39!/(5! 3! 2! 2! 5! 2! 4! 2! 3! 3! 3! 4!) И. Кеплер (1571 – 1630 гг.) опустив 2 буквы, получил: «Salve, umbistineum geminatum Martia proles» («Привет вам, близнецы, Марса порождение»)
8 Общие понятия Он считал, что Галилей открыл спутники Марса, – по аналогии: у Земли – один спутник, у Юпитера – четыре (фактически 16), значит, у Марса их два (так и фактически, но только через 300 лет). Кстати, Галилей действительно включил две дополнительные буквы – для затруднения дешифровки Наконец. X. Гюйгенс (1629 – 1695 гг.) через 50 лет после Галилея распознал кольцо Сатурна и опубликовал такую анаграмму: Aaaaaaa, ccccc, d, еееее, g, h, iiiiiii. (дешифровка вряд ли вообще возможна).
9 Криптография Лишь через 3 года, окончательно убедившись в правильности своих первоначальных заключений, Гюйгенс сообщил действительный смысл анаграммы: «Annulo cingitur, tenui plano, nusquam cohaerente, ad eclipticam inclinato» («Кольцом окружен тонким, плоским, нигде не прикасающимся, к эклиптике наклоненным»).
10 Криптография Простейшая криптограмма - подстановочная. Здесь буквы не перемешиваются (как у Галилея и Гюйгенса), а только заменяются другими буквами. Расшифровка такой криптограммы вполне возможна, особенно если запись достаточно длинная. Используется относительная частота букв (таб.1).
11 Криптография Относительная частота (*10 –3 ) букв русского алфавита Буква Частота Буква Частота Буква Частота 1А6211К2821Ф2 2Б12 Л3522Х9 3В3813М2623Ц4 4Г1314Н5324Ч12 5Д2515О90*25Ш6 6Е, Ё7216П2326Щ3 7Ж717Р4027Ы16 8З 18С4528 Ь, Ъ14 9И6219Т5329 Э3 10Й 20У2130 Ю6 31Я18
12 Криптография Сумма относительных частот составляет 0,836, остальное – частота пробела между словами (0,164). Вообще-то надо бы еще учесть знаки препинания. Итак, самая популярная буква в русском языке – буква «О». Сопоставляя с табличными данными значения относительных частот, полученных путем анализа криптограммы, можно, очевидно, выявить с какой-то долей достоверности происшедшие при формировании криптограммы подстановки-замены. Конечно, запись должна быть статистически представительная (репрезентативная). В неоднозначных ситуациях потребуется, видимо, привлечение и семантических (смысловых) решений.
13 Криптография Перестановочная криптограмма представляет шифр с ключевым словом (ключом). Буквы ключа определяют порядок передачи в кодовую комбинацию (КК) соответствующих им столбцов. Во второй строке табл.2 указаны относительные номера букв ключа в соответствии с алфавитом.
14 Криптография Таблица 2 Пример формирования криптограммы по ключу РИХАРД ВСВЯЗИ ССОЗДА ВШИМСЯ ПОЛОЖЕНИЕМОТ ОДВИГА ЕМСРОК ИВОЗВР АЩЕНИЯ ДОМОЙР АМЗАЙ
15 Криптография В табл. 2 зашифровано сообщение советского разведчика Р. Зорге (запись по строкам): «В связи с создавшимся положением отодвигаем сроки возвращения домой. Рамзай». Передача в линию связи производится по столбцам в порядке : Я 3 М О М И Р 3 Н О А И А Я... Расшифровка на приемной стороне не вызывает трудностей, если известно ключевое слово запись в таблицу - по столбцам, чтение - по строкам. Ясно, что частотный анализ принятого текста не решает здесь задачу дешифровки.
16 Криптография Подстановочное и перестановочное кодирования могут быть совмещены (в любой комбинации) Еще один способ кодирования связан с представлением каждой буквы несколькими (2, 3,...) символами (табл.3). Таблица символьное кодирование ИЫРС 1АТУЙЬЭ 2БВФКЛ 3МЮЯГХЦ 4ЧНОДЕ 5ЖШЩП
17 Криптография Буква «Б» в соответствии с табл.3 получает кодовое представление 21 и т д. Заметна аналогия с таблицами кодов символов, используемых в ЭВМ, например ASCII и т.п. Разница в том, что здесь таблица кодов – нестандартная. Комбинированный способ представляет шифр Тритемиуса (расширение кода Цезаря). В русской интерпретации это выглядит так. Буквы алфавита нумеруются: k, l = (табл.1). Ключевое слово циклически повторяется в наложении на кодируемый текст:
18 Криптография Здесь m = к + l (mod 31), т.е. m – вычет суммы к + l по модулю 31, или остаток от деления этой суммы на 31. Например, 17(С) + 16(Р) = 33 = 2 (mod 31). В линию связи передается, таким образом, колония комбинация ТЩЧЯЧМВЩ … На приемной стороне дешифрация осуществляется по правилу: k = m – l (mod 31).
19 Криптография Например, 30(Я) – 0(A) = 30 (mod 31) означает прием буквы Я (четвертая буква КК), a 2(B) – 16(Р) = –14 = 17 (mod 31) – прием буквы С (седьмая буква). Здесь надо учесть смешение нумерации букв (табл.1) на (–1). Ключевое слово на приемной стороне циклически повторяется в наложении на принятую кодовую комбинацию. Конечно, существует огромное множество других, более мощных способов засекречивания информации. Например, кодирование с «открытым» и «закрытым» ключами. В последнем случае ключ заранее неизвестен, а передастся источником сообщений вместе с основной информацией. Правда, теперь возникает опасность «перехвата» этого ключа.
20 Эффективное кодирование Эффективное кодирование рассматривается в отсутствие помех. Речь идет о сокращении объема передаваемой информации, т.е. о достижении минимального уровня избыточности. Количество информации принято связывать с понятием энтропии. Энтропия - это степень хаотичности (греч. - поворот, превращение). Максимальная энтропия – в состоянии равновесия. В физике (термодинамике) – это состояние полного хаоса. Вообще-то ясно, что для описания многообразия требуется большее количество информации, чем в случае однообразия (тогда и энтропия минимальная).
21 Эффективное кодирование При передаче сообщений с двоичным кодированием символов {z i } энтропия определяется в соответствии с формулой: l = Z (мощность множества Z – количество символов z i ). Действительно, если передается одно двоичное значение 0 или 1 с вероятностью 1/2, то объем информации (энтропия) составляет: 2 (- 0,5 log 2 1/2) = 2 (- 0,5 (–1)) = 1 (бит).
22 Эффективное кодирование Эффективное, или экономичное, кодирование означает достижение минимального значения средней длины кода символа Доказано, что n ср не может быть меньше чем энтропия: n Н (Z). В телеграфии широко известна так называемая азбука Морзе. Сокращение n ср здесь достигается за счет назначения часто встречающимся символам коротких кодов (одна «точка» или одно «тире»). Наоборот, редкие символы имеют длинные коды.
23 Эффективное кодирование Противоположность азбуке Морзе представляет код Боло. Каждый символ кодируется 5 двоичными разрядами (нормальное кодирование, длина кода постоянная величина). Кодирование по методу Шеннона - Фано не абсолютно оптимальное, но достаточно эффективное. Процедура кодирования циклическая. 1. Символы z i упорядочиваются по убыванию частоты – вероятности p i. 2. Множество Z разбивается на 2 группы символов, так чтобы общие вероятности в этих группах были как можно ближе (р 1 р 2 ), причем вообще-то неважно: р 1 р 2 или р 1 р В коды символов первой группы вписывается 0, в коды второй группы – 1. После этого действия 2 и 3 повторяются.
24 Эффективное кодирование Т.е. далее следует новое деление в каждой группе: р 1 = р 11 + р 12, р 2 = р 21 + р 22, и т.д. до тех пор, пока очередные группы не окажутся односимвольными (табл.4). Здесь каждое разбиение-деление осуществляется точно - ровно пополам. При этом в верхней группе всегда получается единственный символ, для него в коде формируется нуль, в нижней группе все символы получают единицу. Средняя длина кода (табл.4) n ср = /64. Кстати, и значение энтропии точно такое же, поскольку n 1 p 1 = –p 1 log 2 p 1, или n 1 = –log 2 p 1.
25 Эффективное кодирование Пример кодирования Шеннона – Фано Таблица 4
26 Эффективное кодирование Нормальное двоичное кодирование в рассмотренном примере дало бы худший результат n норм = int log 2 8 = 3 > /64. Кодовое дерево (граф) получается бинарное (из каждой вершины, кроме конечных, выходят 2 ребра.
27 Эффективное кодирование Код символа формируется в ходе следования по маршруту из корня (верхняя вершина) до соответствующего листа. Кодирование по методу Шеннона-Фано может быть не обязательно двоичное. Если код троичный, разбиение на каждом шаге должно быть на 3 группы. Хотя на последнем шаге групп (подгрупп) может быть всего две (табл.5).
28 Эффективное кодирование Таблица 5.5 Троичное кодирование Шеннона - Фано
29 Эффективное кодирование Кодирование по методу Хаффмена (А.Д. Хаффмен – американский математик; работа – 1952 г.) гарантирует оптимум для заданного множества {р i }. Процедура кодирования циклическая и более сложная, чем у Шеннона - Фано. 1. Символы z i упорядочиваются по убыванию вероятности pi. 2. Два последних (нижних в табл.6) символа объединяются в группу-пару, соответствующую вспомогательному символу с суммарной вероятностью. Если суммируемые вероятности представляют исходные значения p i, это специально отмечается («*»). Здесь – конец формирования кода соответствующего символа. Далее пп. 1 и 2 повторяются. При этом в общем случае происходит переупорядочивание вероятностей p i. В конце концов суммарная вероятность достигает значения 1 и процесс заканчивается.
30 Эффективное кодирование Таблица 6 Пример кодирования но Хаффмену
31 Эффективное кодирование Теперь строится кодовое дерево. Вершины дерева отмечены соответствующими вероятностями (меньшая - слева). Теперь по кодовому дереву могут быть сформированы коды всех символов – спуск из корневой вершины, где вероятность 1.00 (табл.7).
32 Эффективное кодирование Таблица 7 Кодирование Хаффмена ZiZi pipi Кодnini nipinipi Z1Z Z2Z Z3Z Z4Z Z5Z Z6Z Z7Z Z8Z
33 Эффективное кодирование n ср = 2,75 < 3. Можно проверить, в рассмотренном примере кодирование по методу Шеннона - Фано дает такой же результат. Преимущество кодирования по Хаффмену на такой короткой «дистанции» (8 символов) не выявилось. Конечно, кодирование и здесь может быть троичное,....
34 Помехоустойчивое кодирование Борьба с помехами, вносимыми в линию связи (рис.1), требует введения избыточности в кодовую комбинацию (КК): кроме информационных разрядов формируются и передаются контрольные (проверочные) разряды. Пусть при длине КК n двоичных разрядов m разрядов - информационные, k – контрольные. Тогда избыточность помехоустойчивого (корректирующего) кода составит Значения R заключены в диапазоне от 0 (k = 0) до почти 1 (k >>m).
35 Помехоустойчивое кодирование Корректирующая способность помехоустойчивого кода оценивается двумя параметрами: кратность обнаруживаемых ошибок. Q обн ; кратность исправляемых ошибок, Q испр. Наиболее популярными способами помехоустойчивого кодирования являются: многократная передача; контроль по нечетности (четности); контрольное суммирование; кодирование по Хеммингу
36 Помехоустойчивое кодирование В первом способе кодовая комбинация передается минимум 2 раза. Если принятые значения совпадают, все в порядке. Если нет, запрашивается еще 1 передача, и далее действует мажоритарный принцип – решение принимается по большинству (2 > 1 и т.п.). Способ многократной передачи – самый избыточный. Элемент его – перезапрос кодовой комбинации присутствует и в других способах помехоустойчивого кодирования - когда ошибка только обнаруживается, но не исправляется.
37 Помехоустойчивое кодирование Контроль по нечетности (четности)- один из самых простых и распространенных. Обычно каждый байт (8 двоичных информационных разрядов) дополняется разрядом- битом так называемого паритета (parity). Значение этого разряда получается как дополнение количества единиц в байте до нечетного (четного) числа. Например, байт содержит 5 (нечетное) число единиц, поэтому при контроле по нечетности в разряде паритета (KN) - нуль: 8 KN = хi i = 1
38 Помехоустойчивое кодирование Выполняется, таким образом, простейшая операция свертки по модулю 2. При контроле по четности в этом разряде было бы значение 1: Избыточность кода нечетности-четности невелика: R = 1/9 0,11. Невелика и корректирующая способность этого кода – ошибки могут только обнаруживаться, причем нечетной кратности (1, 3, 5, 7), но не исправляются (Q испр = 0). Еще один недостаток – ложная тревога. Ошибка случилась в контрольном разряде, информационные - в порядке. Но несмотря на это, будет сделан перезапрос кодовой комбинации.
39 Помехоустойчивое кодирование Контроль по нечетности предпочтительнее контроля по четности в случае представления информации, например, на магнитной ленте. Байты информации с контрольными разрядами размещаются на ленте в поперечном направлении и требуют 9 дорожек. При контроле по четности необходима еще одна дорожка – для синхроимпульсов. Появление синхроимпульсов определяет момент считывания байта, т.е. момент его прохождения под остальными 9 головками. Контроль по нечетности, реализуемый в накопителях на магнитной ленте ЭВМ, не требует дорожки с синхроимпульсами. Дело в том, что 9-разрядный байт в этом случае не может быть полностью нулевым (хотя бы одна единица в нем есть). Прохождение под головками любого из единичных бит вызывает срабатывание «триггера первого бита» и фиксирует, таким образом, момент считывания. Интересно, что в первых ПЭВМ контроль по нечетности- четности не производился, соответствующие линии и сигналы в интерфейсах отсутствовали. Теперь картина изменилась. Это связано, очевидно, с ухудшением качества передающей среды (повышенная частота и т.п.).
40 Помехоустойчивое кодирование Контрольное суммирование - тоже довольно «древний» способ. Байты (слова) на магнитной ленте (диске) суммируются совершенно формально как представляющие числа без знака. В старых машинах, где использовался обратный код, это суммирование выполнялось с циклическим переносом (из старшего разряда в младший). Контрольная сумма, полученная при записи, сравнивалась с полученной при чтении. Естественно, ошибки могли только обнаруживаться, но не исправляться, т.е осуществлялся при необходимости перезапрос КК (повторный ввод с ленты или диска). Контрольная сумма могла передаваться на носитель в конце записи, или на ленту (диск) записывалось дополнение до нулевого значения обшей суммы (включая строку с собственно контрольной суммой). В последнем случае контроль облегчался: сравнение – всегда с нулем
41 Помехоустойчивое кодирование Кодирование по Хеммингу позволяет не только обнаруживать ошибки, но и исправлять их. Например, модифицированный код Хемминга (КХМ) способен обнаруживать двойные ошибки, а также ошибки нечетной кратности, плюс к этому - исправлять одиночные ошибки: Q обн =1, 2, 3, 5, …, Q испр = 1.
42 Помехоустойчивое кодирование Кстати, считается, что вероятность ошибки двойной и большей кратности значительно меньше вероятности ошибки одиночной (и это хорошо!). Ошибка может случиться в любом разряде кода Хеммингa (KX) - информационном (И) или контрольном (К). Позиции контрольных (проверочных) разрядов КХ, в отличие от кода нечетности, важны. Они имеют строго определенные номера Значения контрольных разрядов формируются передатчиком на основе разрядов информационного слова с помощью кодирующей (порождающей) матрицы.
43 Помехоустойчивое кодирование На приемной стороне они вместе с информационными разрядами обрабатываются с помощью проверочной матрицы. Обычно эти две матрицы совпадают (может быть, частично). Количество проверок, в которых участвуют все разряды КК, равно количеству контрольных разрядов кода, т.е. k. Результат каждой проверки двоичный (0 или 1). Самая подходящая операция здесь – сложение (свертка) по модулю 2. Эти 0 или 1 представляют значение некоторого бита синдрома ошибки S. Разрядность синдрома, таким образом, составляет k. Значение S как раз и определяет номер позиции КХ с одиночной ошибкой. Т.е. все дальнейшее ориентируется именно на случай одиночной ошибки, которая, таким образом, исправляется – с помощью простой инверсии разряда с номером S.
44 Помехоустойчивое кодирование Отсутствие ошибки в разрядах, охваченных некоторой проверкой, соответствует значению бита синдрома, равному 0, наличие – 1. Значение S = интерпретируется как «Нет ошибок». Вариантов одиночной ошибки вместе со случаем S = 0 – всего n + 1: Нет ошибок Ошибка в правом (младшем) разряде 0 … … … … Ошибка в левом (старшем) разряде _______ n
45 Помехоустойчивое кодирование Очевидно, необходимо, чтобы количество различных значений синдрома S было не меньшим чем n + 1: 2 k 2n + 1, 2 n–m n + 1, 2 n / (n + 1) 2 m.
46 Помехоустойчивое кодирование Задаваясь значением n длины кодовой комбинации, можно определить максимальное значение m количества информационных разрядов (табл.8). Параметры кода Хемминга Таблица 8 n … m …
47 Помехоустойчивое кодирование Действительно, например для n = 8: Представляет интерес случай m = 64 (8 байтов - распространенное значение ширины выборки из оперативной памяти): 2 k 65 + k, k 7.
48 Помехоустойчивое кодирование Таким образом, к 64 информационным разрядам нужно добавить 7 контрольных разрядов. В модифицированном коде Хемминга (с повышенной корректирующей способностью) есть еще один, дополнительный контрольный разряд (КД), получается всего 8 контрольных разрядов, и n = = 72. Именно столько разрядов получается при контроле по нечетности (8 разрядов дополнения до нечетного количества единиц в 9-разрядном байте). Этот факт используется, когда в оперативной (и даже в КЭШ-) памяти действует кодирование по Хеммингу (КХМ), а снаружи - кодирование по нечетности. Конечно, на входе и выходе памяти требуется осуществлять преобразование кодов: нечетность-Хемминга - нечетность.
49 Помехоустойчивое кодирование Рассмотрим для простоты случай n = 7 (m = 4, k = 3, табл.8). Если ошибка действительно одиночная и S – номер ошибочного разряда, в примере – 3-разрядный (001 2 … ~ 1 … 7, S = S 3 S 2 S 1(2)), то в выражение для S должны входить разряды КК, номера которых содержат 1 в младшем двоичном разряде, т. е. в разряде «2 0 ». Аналогично, в выражение для S 2 входят разряды с номерами, имеющими 1 в разряде «2 1 » для S 3 – в разряде «2 2 » Таким образом, S 1 = , S 2 = , S 3 = Здесь указаны условно, вместо, например, d 1... d 7. Действительно, двоичные коды 1 = 001 2, 3 = 011 2, 5 = 101 2, 7 = содержат 1 в разряде «2 0 ». И т. д.
50 Помехоустойчивое кодирование Теперь нужно решить вопрос о выборе позиций в КК для размещения контрольных разрядов. В примере – это К 3, К 2, К 1. Лучше для уменьшения вероятности ложной тревоги (когда ошибка – в одном из контрольных разрядов) выбрать разряды КК, участвующие в наименьшем количестве проверок. В примере – это, очевидно, разряды 1, 2 и 4. Продолжая по аналогии, получим 8, 16, 32,....
51 Помехоустойчивое кодирование Итак, структура кодовой комбинации образована: И 4 И 3 И 2 И 1 К 3 К 2 К Всего разрядов 7, 3 из них – контрольные. Кстати, избыточность довольно большая: R = 3/7 = 0,43. Она же характеризуется и тем, что из 2 7 = 128 (возможных) КК всего 2 4 = 16 полезных, используемых.
52 Помехоустойчивое кодирование Рассмотрим пример передачи слова И 4 И 3 И 2 И 1 = Кодирующая и проверочная матрицы строятся на основе прямоугольной матрицы Н, имеющей k строк и n столбцов:
53 Помехоустойчивое кодирование В матрице Н справа налево в столбцах представлены последовательные двоичные числа Для определения значений контрольных разрядов достаточно сокращенной матрицы, в ней остаются только столбцы, соответствующие информационным разрядам.
54 Помехоустойчивое кодирование Процедура кодирования выглядит так: – информационное слово последовательно накладывается на строки кодирующей матрицы; – выполняется операция поразрядной конъюнкции; – результаты конъюнкции суммируются по модулю 2 (по строке). Таким образом, получается: K 1 = = = 0, K 2 = = = 0, K 3 = = = 1.
55 Помехоустойчивое кодирование В результате кодирования в линию связи передается такая кодовая комбинация КХ: И ~ К 1 00 На приемной стороне реализуется процедура декодирования. При этом в качестве декодирующей матрицы используется полная матрица Н.
56 Помехоустойчивое кодирование Процедура декодирования выполняется аналогично процедуре кодирования, но теперь вместо информационного слова рассматривается вся кодовая комбинация и вычисляются значения не контрольных разрядов, а битов синдрома ошибки:
57 Помехоустойчивое кодирование Получается: S 1 = = 1 (3 5 7) = K 1 K 1 = 0, S 2 = = K 2 K 2 = 0, S 3 = = K 3 K 3 = 0. Действительно, в отсутствие ошибок синдром S - нулевой (000).
58 Помехоустойчивое кодирование Теперь, пусть случилась одиночная ошибка - искажен разряд 5: KK = Очевидно, теперь значения битов синдрома S 1 и S 3 изменятся (писать здесь К 1 К 1 = 0, К 3 К 3 = 0 нельзя): S 1 = = 1, S 3 = = 1, S = = 5. Таким образом, позиция ошибки установлена точно, исправление сводится к инверсии И 2 :
59 Помехоустойчивое кодирование Повышение корректирующей способности КХ связано с его модификацией (КХМ). Двойная ошибка будет обнаруживаться, как и все ошибки нечетной кратности. В кодовой комбинации появляется дополнительный контрольный разряд КД, фактически – это разряд контроля по четности (разряд «двойного контроля»): КД = х i = i Позиции КД - не фиксированная, удобно, например, задать ее справа - в разряде 0. В примере КД = 0.
60 Помехоустойчивое кодирование На приемной стороне вычисляется дополнительный бит синдрома SД: SД = = КД КД = 0 (в отсутствие ошибок нечетной кратности). Ошибка четной кратности, в том числе двойная, общую четность КК не нарушает, и SД = 0 (табл.9). В примере (с ошибкой в разряде 5) КД = 0, SД = 1.
61 Помехоустойчивое кодирование Таблица 9 Ситуации на приемной стороне SДSДБиты S. кроме SД Интерпретация 10Все 0Нет ошибок 20Есть 1Двойная ошибка (обнаруживается) 31Все 0Ошибка в КД (ложная тревога) 41Есть 1Одиночная ошибка (исправляется)
62 Помехоустойчивое кодирование К табл.9 необходимо сделать, по крайней мере, такие уточнения: «Нет ошибок», точнее - они не обнаружены: «Двойная ошибка», точнее - четной кратности (табл.10), «Одиночная ошибка», точнее - ошибка нечетной кратности (табл.10). Видно, что исправление «одиночной» ошибки, когда на самом деле это ошибка кратности 3, 5,..., ухудшает ситуацию, поскольку перезапрос кодовой комбинации не делается. Таким образом, обнаружение ошибок нечетной кратности 3, 5,... не совсем корректно.
63 Помехоустойчивое кодирование Таблица 5.10 Примеры ошибочных ситуаций Кратность ошибки 1234 Оши 6 очные разряды 5 5, 07, 5, 07, 5, 4, 0 КК (передача) КК (прием) S3 S2S1S3 S2S SДSД1010 Интерпретация ОдиночнаяДвойная ОдиночнаяДвойная Соответствие факту Точное Условное
64 Лекция окончена Нажмите клавишу для выхода
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.