Практическое-занятие. Исследование принципов помехоустойчивого кодирования на примере
 Скачать 1.17 Mb.
|
|
Практическое занятие №3 Тема: Исследование принципов помехоустойчивого кодирования на примере корректирующих кодов Хемминга. При передаче информации по каналу связи с помехами в принятых данных могут возникать ошибки. Если такие ошибки имеют небольшую величину или возникают достаточно редко, информация может быть использована потребителем. При большом числе ошибок полученной информацией пользоваться нельзя. Ранее уже говорилось о понятии помехоустойчивости (способности информационных систем противостоять воздействию помех). Для реализации принципа помехоустойчивости информационных систем может быть использовано помехоустойчивое кодирование. Помехоустойчивыми (корректирующими) называются коды, позволяющие обнаружить и при необходимости исправить ошибки в принятом сообщении. Возможность использования кодирования для уменьшения числа ошибок в канале была теоретически показана К. Шенноном в 1948 году в его работе "Математическая теория связи". Теперь это утверждение принято именовать второй теоремой Шеннона. Задача о разведчиках 1 . Разведывательный отряд в составе командира и восьми бойцов высадился на вражеском острове вблизи перекрестка, откуда исходят дороги по четырем направлениям. Задача отряда – обнаружить секретный объект противника. Об объекте известно, что он расположен на одной из 4-х дорог в часе ходьбы от перекрестка. Командиру известно, что двое из его бойцов – предатели, которые будут стараться обмануть командира, чтобы не допустить обнаружения объекта. Необходимо спланировать действия командира по обнаружению объекта и предателей. К этой задаче мы будет обращаться многократно. Для указания на то, что рассматривается задача о разведчиках, будем использовать символ . Общие принципы помехоустойчивого кодирования. Хотя различные схемы кодирования очень непохожи друг на друга и основаны на различных математических теориях, всем им присущи два общих свойства. Первое − использование избыточности. Закодированные последовательности всегда содержат дополнительные, или избыточные, символы. Второе — свойство усреднения, означающее, что избыточные символы зависят от нескольких информационных символов, то есть информация, содержащаяся в кодовой последовательности X, перераспределяется также и на избыточные символы. Пусть M – число знаков первичного алфавита. Длина равномерного двоичного кода K ≥ log 2 M – при этом каждый знак получает свою уникальную последовательность знаков вторичного алфавита. Общее число кодовых комбинаций S р = 2 K , очевидно, S р M. 1 Автор сюжета задачи – К.Кноп. См. Константин Кноп. О разведчиках и кодах Хемминга / Компьютера, 1997, №6. Например, мощность алфавита – М=40. Длина равномерного бинарного кода K log 2 M = 6 . С помощью 6 бит можно получить 2 6 =64 кодовых комбинаций. Они будут считаться разрешенными, хотя некоторые из них и не соответствуют символам исходного алфавита. В дальнейшем будем называть часть помехоустойчивого кода, составленную из указанных k бит, информационной (поскольку именно они содержат информацию о передаваемом знаке первичного алфавита). Если пересылать только эти информационные биты, то любое искажение, состоящее в инверсии хотя бы одного бита, приведет к появлению новой разрешенной кодовой комбинации и, следовательно, обнаружено быть не может. Сколько информационных бит потребуется командиру разведчиков? Ответ: сообщение от одного разведчика о том, что на дороге обнаружен разыскиваемый объект, будем обозначать 1, а отсутствие объекта на дороге – 0 . Для обнаружения объекта достаточно получить информацию о наличии/отсутствии объекта с трех дорог. Следовательно, количество информационных разрядов равно 3. Возможность обнаружения и исправления ошибок в помехоустойчивых кодах достигается тем, что после первичного кодирования (установления соответствия каждому знаку первичного алфавита его кода) осуществляется вторичное кодирование, в ходе которого к k информационным битам по определенным правилам добавляются r проверочных (корректирующих) бит. В результате общая длина кодовой комбинации становится равной n = k + r – в дальнейшем такие коды будем называть (n,k)-кодами, а число возможных кодовых комбинаций возрастает до S = 2 n . Из них не все оказываются разрешенными – их только S р , остальные же S f = S – S р комбинаций являются запрещенными. Например, мощность алфавита – М=40. Количество информационных бит k ≥ log 2 M = 6. С помощью 6 бит можно получить 2 6 =64 разрешенных кодовых комбинаций. Допустим, помехоустойчивый код содержит 3 проверочных бита. Общая длина кодового слова будет равна 6+3=9 бит, а общее количество кодов S=2 9 =512 . Из них разрешенных кодов – 64, а запрещенных – 448. Командир по одной дороге идет сам, по остальным посылает разведчиков. Определить количество проверочных битов. Ответ: Всего командир получит от бойцов 8 однобитных сообщений, три из них – информационные, остальные 5 – проверочные. Если при передаче возникает ошибка, она проявится в том, что разрешенная кодовая комбинация перейдет в запрещенную – это можно отследить и даже исправить. Такое обнаружение, очевидно, окажется невозможным, если в результате ошибки передачи одна разрешенная кодовая комбинация перейдет в другую разрешенную. В связи с этим возникает проблема поиска таких способов избыточного кодирования, при которых вероятность перехода одной разрешенной кодовой комбинации в другую была бы минимальной. Классификация помехоустойчивых кодов Рис. Классификация помехоустойчивых кодов. Первый классификационный признак – коды бывают блочными или непрерывными. При блочном кодировании передаваемые двоичные сообщения сгруппированы в блоки, которыми кодируются знаки (или группы знаков) первичного алфавита. В блоке присутствуют информационные и проверочные биты. Известно, что если все кодовые комбинации имеют одинаковую длину, код называется равномерным; если нет – неравномерным. При декодировании удобнее (проще) иметь дело с равномерным кодом, поэтому именно он, как правило, используется в помехоустойчивом кодировании. Непрерывные (синонимы: цепные, сверточные, рекуррентные) коды представляют собой непрерывную последовательность бит, не разделяемую на блоки (информационные и проверочные биты в них чередуются по определенному правилу). Блочное кодирование удобно использовать в тех случаях, когда исходные данные по своей природе уже сгруппированы в какие-либо блоки или массивы. При передаче по радиоканалам чаще используется сверточное кодирование, которое лучше приспособлено к побитовой передаче данных. Кроме этого, при одинаковой избыточности сверточные коды, как правило, обладают лучшей исправляющей способностью. Второй классификационные признак, относящийся как к блочным, так и к непрерывным кодам, подразделяет коды на разделимые и неразделимые. Разделимыми называются коды, в которых информационные и проверочные биты располагаются в строго определенных позициях. В неразделимых кодах такой определенности нет, что затрудняет их кодирование и декодирование. Поэтому практический интерес представляют в основном разделимые коды, а из неразделимых – только коды с постоянным весом. Третий классификационный признак относится только к блочным разделимым кодам – они подразделяются на систематические (линейные) и несистематические. Двоичный код является линейным, если сумма по модулю 2 (mod2) двух кодовых слов также является кодовым словом этого кода. В линейных кодах проверочные биты являются результатом линейных операций над информационными разрядами. В несистематических (нелинейных) кодах информационные и проверочные биты либо вообще не имеют связи, либо эта связь нелинейна – такие коды применяются крайне редко. Наиболее часто в линиях связи используются блочные линейные коды, называемые (n, k)-коды, к которым относятся циклические, коды Хемминга, матричные канонические и ряд других. Примеры простейших кодов Код с проверкой на четность. Самым простым линейным блочным кодом является (n,n-1)-код, построенный с помощью одной общей проверки на четность. Например, кодовое слово (4,3)-кода можно записать в виде вектора-столбца: U T = (m 0 , m 1 , m 2 , m 0 m 1 m 2 ), где m i - символы исходной информационной последовательности, принимающие значения 0 и 1, а суммирование производится по модулю 2 и обозначается символом Основная идея проверки на четность состоит в следующем. Пусть информационная последовательность источника имеет вид m = (1 0 1). Тогда соответствующая ей кодовая последовательность будет выглядеть так: U = (u 0 , u 1 , u 2 , u 3 ) = (1 0 1 0), где проверочный символ u 3 формируется путем суммирования символов информационной последовательности m: u 3 = m 0 m 1 m 2 = 1 0 1 = 0. Если число единиц в последовательности mчетно, то результатом суммирования будет 0, если нечетно — 1, то есть проверочный символ дополняет кодовую последовательность таким образом, чтобы количество единиц в ней было четным. При передаче по каналам связи в принятой последовательности возможно появление ошибок, то есть символы принятой последовательности могут отличаться от соответствующих символов переданной кодовой последовательности (нуль переходит в единицу, а 1 − в 0). Если при передаче рассматриваемого (4,3)-кода произошла одна ошибка, причем неважно, в какой его позиции, то общее число единиц в принятой последовательности уже не будет четным. Таким образом, признаком отсутствия ошибки в принятой последовательности может служить четность числа единиц. Поэтому такие коды и называются кодами с проверкой на четность. Правда, если в принятой последовательности произошло две ошибки, то общее число единиц в ней снова станет четным и ошибка обнаружена не будет. Однако вероятность двойной ошибки значительно меньше вероятности одиночной, поэтому наиболее вероятные одиночные ошибки таким кодом обнаруживаться все же будут. Отметим следующий момент. Если посимвольно сложить два кодовых слова, принадлежащих рассматриваемому (4, 3)-коду: a = (a 0 , a 1 , a 2 , a 0 a 1 a 2 ), иb = (b 0 , b 1 , b 2 , b 0 b 1 b 2 ), то получим с = (a 0 b 0 , a 1 b 1 , a 2 b 2 , a 0 b 0 a 1 b 1 a 2 b 2 ) = (c 0 , c 1 , c 2 , c 0 c 1 c 2 ), то есть проверочный символ в новом слове с определяется по тому же правилу, что и в слагаемых. Поэтому стакже является кодовым словом данного кода. Этот пример отражает важное свойство линейных блочных кодов — замкнутость, означающее, что сумма двух кодовых слов данного кода также является кодовым словом. Несмотря на свою простоту и не очень высокую эффективность, коды с проверкой на четность широко используются в системах передачи и хранения информации. Они ценятся за невысокую избыточность: достаточно добавить к передаваемой последовательности всего один избыточный символ − и можно узнать, есть ли в принятой последовательности ошибка. Правда, определить место этой ошибки и, следовательно, исправить ее, пока нельзя. Можно лишь повторить передачу слова, в котором была допущена ошибка, и тем самым ее исправить. Итеративный код. Еще одна простая схема кодирования, которая также часто используется, может быть построена следующим образом. Предположим, что нужно передать, к примеру, девять информационных символов m = (m 1 , m 2 , ..., m 9 ). Эти символы можно расположить в виде квадратной матрицы, как это показано в таблице, и добавить к каждой строке и каждому столбцу этой таблицы по проверочному символу (проверка на четность). m 1 m 2 m 3 m 1 m 2 m 3 m 4 m 5 m 6 m 4 m 5 m 6 m 7 m 8 m 9 m 7 m 8 m 9 m 1 m 4 m 7 m 2 m 5 m 8 m 3 m 6 m 9 m 1 m 2 m 3 … m 9 Таким образом, по строкам и по столбцам этой таблицы будет выполняться правило четности единиц. Если в процессе передачи по каналу с помехами в этой таблице произойдет одна ошибка (например, в символе m 4 ), то проверка на четность в соответствующей строке и столбце не будет выполняться. Иными словами, координаты ошибки однозначно определяются номерами столбца и строки, в которых не выполняются проверки на четность. Таким образом, этот код, используя различные проверки на четность (по строкам и по столбцам), способен не только обнаруживать, но и исправлять ошибки (если известны координаты ошибки, то ее исправление состоит просто в замене символа на противоположный: если 0, то на 1, если 1 – то на 0). Описанный метод кодирования, называемый итеративным, оказывается полезным в случае, когда данные естественным образом формируются в виде массивов, например, на шинах ЭВМ, в памяти, имеющей табличную структуру, и т.д. При этом размер таблицы в принципе не имеет значения (3×3 или 20×20), однако в первом случае будет исправляться одна ошибка на 3×3=9 символов, а во втором – одна на 20×20=400 символов. Если в простом коде с проверкой на четность для обнаруженияошибки приходится добавлять к информационной последовательности всего один символ, то для того, чтобы код стал исправлять однократную ошибку, понадобилось к девяти информационным символам добавить еще семь проверочных.Таким образом, избыточность этого кода оказалась очень большой, а исправляющая способность – сравнительно низкой. Поэтому усилия специалистов в области помехоустойчивого кодирования всегда были направлены на поиск таких кодов и методов кодирования, которые при минимальной избыточности обеспечивали бы высокую исправляющую способность. Порождающие матрицы блочных кодов Только что в качестве примера были рассмотрены два простейших корректирующих кода - код с простой проверкой на четность, позволяющий обнаруживать однократную ошибку в принятой последовательности, и блочный итеративный код, исправляющий одну ошибку с помощью набора проверок на четность по строкам и столбцам таблицы. Зададим формальные (порождающие) правила, по которым осуществляется кодирование, то есть преобразование информационной последовательности в кодовое слово. Простейшим способом описания, или задания, корректирующих кодов является табличный способ, при котором каждой информационной последовательности просто назначается кодовое слово из таблицы кода. m U 000 0000 001 0011 010 0101 011 0110 100 1001 101 1010 110 1100 111 1111 Такой способ описания кодов, кстати, применим для любых, а не только линейных кодов. Однако при больших k размер кодовой таблицы оказывается слишком большим, чтобы им пользоваться на практике. Другим способом задания линейных блочных кодов является использование так называемой системы порождающих уравнений, определяющих правило, по которому символы информационной последовательности преобразуются в кодовые символы. Для того же примера система порождающих уравнений будет выглядеть следующим образом: u 1 = m 1 , u 2 = m 2 , u 3 = m 3 , u 4 = m 1 m 2 m 3 Однако наиболее удобным и наглядным способом описания линейных блочных кодов является их задание с использованием порождающей матрицы, являющейся компактной формой представления системы проверочных уравнений. Линейный блочный (n,k)-код полностью определяется матрицей G размером k n с двоичными матричными элементами. При этом каждое кодовое слово является линейной комбинацией строк матрицы G, а каждая линейная комбинация строк G – кодовым словом. Обычно порождающие матрицы выглядят так: k n , k 2 k 1 k k n , 2 22 21 k n , 1 12 11 P ... P P 1 ... 0 0 P ... P P 0 ... 1 0 P ... P P 0 ... 0 1 G Например, для (4,3)-кода с проверкой на четность порождающая матрица будет иметь вид: 1 1 0 0 1 0 1 0 1 0 0 1 G Пусть m = (m 1 , m 2 ,… ,m k ) будет тем блоком-сообщением, который необходимо закодировать с использованием данного кода. Тогда соответствующим ему кодовым словом U будет U = m G С учетом структуры матрицы G символы кодового слова U будут такими: для i = 1, 2,... , k: u i = m i ; для i = k+1,... , n: u i = m 1 P 1,i-k m 2 P 2,i-k m 3 P 3,i-k … m k P k,i-k . Иными словами, k крайних левых символов кодового слова совпадает с символами кодируемой информационной последовательности, а остальные (n - к) символов являются линейными комбинациями символов информационной последовательности. Например, если входная последовательность кодера m = (1 0 1), то с применением порождающей матрицы код будет построен так: 0 1 0 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 G m U Командир послал трех разведчиков по первой дороге, трех – по второй, двух – по третьей, по четвертой пошел сам. Составить порождающую матрицу такого кода. Ответ: по сюжету задачи сообщение, полученное командиром лично, не может быть искаженным. Поэтому ограничимся исследованием информации, передаваемой бойцами. Следовательно: 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 G Определенный таким образом код называется линейным блочным систематическим (n,k)-кодом с обобщенными проверками на четность, а задающая его матрица G называется порождающей матрицей кода. Характеристики блочных линейных кодов Напомним для начала, что двоичный код – это код с основанием 2. Количество разрядов в каждой кодовой комбинации (блоке) называют длиной или значностью кода и обозначают n. Символы каждого разряда могут принимать значения 0 или 1. Количество единиц в кодовой комбинации называют весом и обозначают ω. Например, кодовая комбинация 100101100 имеет значность n = 9 и вес ω = 4. Степень отличия двух любых кодовых комбинаций характеризуется кодовым расстоянием d (расстоянием Хемминга), которое определяется как число разрядов, в которых комбинации отличаются одна от другой. Для определения кодового расстояния надо просуммировать (по модулю 2) две кодовые комбинации и определить вес суммы. Пример. Определить кодовое расстояние между комбинациями 100101100 и 110110101. Просуммируем: 010011001 110110101 100101100 Вес полученной суммы (количество единиц) ω=4, следовательно, кодовое расстояние d=4. Определить все кодовые расстояния между безошибочными комбинациями сообщений разведчиков. Ответ: расстояние между первой и второй строкой порождающей матрицы – 6, между первой и третьей – 5, между второй и третьей – 5. При передаче в кодовых комбинациях возникают ошибки типа «инверсия». Если ошибка произошла в одном разряде блока, она называется однократной, при ошибках в двух, трех и т.д. разрядах они называются двукратными, трехкратными и т.д. Для описания возникающих в канале ошибок используют вектор ошибки, обычно обозначаемый как e и представляющий собой двоичную последовательность длиной nс единицами в тех позициях, в которых произошли ошибки. Вес вектора ошибки равен кратности ошибки. Так, вектор ошибки e = (0 0 0 1 0 0 0) означает однократную ошибку в четвертом разряде (четвертом бите), вектор ошибки e = (1 1 0 0 0 0 0) - двукратную ошибку в первом и втором битах и т.д. Допустим, по каналу связи передается кодовое слово U , в результате принята последовательность Û, возможно, содержащая ошибки. Если е – вектор ошибок, тоÛ = U e,или, что то же самое, e = U Û, U = Û e. Помехоустойчивость кодирования обеспечивается за счет введения избыточности. Это значит, что из n символов кодовой комбинации для передачи информации используется k < n символов. Коэффициент избыточности кода – это отношение количества проверочных битов к длине кода. n k n F При длине кодового слова n всего возможных кодовых слов – 2 n , из них безошибочными могут быть 2 k . Соответственно, все множество кодовых комбинаций разбивается на две группы: разрешенные комбинации и запрещенные комбинации. Разрешенных комбинаций S р = 2 k , запрещенных S f = S – S р =2 n - 2 k . Если на приемной стороне установлено, что принятая комбинация относится к разрешенным, то считается, что сообщение прошло без искажений, а если принята запрещенная комбинация, то делается вывод, что произошла ошибка. Однако, если ошибка такова, что посланная комбинация, претерпев искажения, тем не менее, попала во множество разрешенных комбинаций, такая ошибка обнаружена не будет. Пусть всего S р разрешенных комбинаций. Каждая из них при передаче может трансформироваться в любую из S возможных комбинаций, т.е. всего имеется S·S р возможных вариантов передачи. Из них S р вариантов безошибочной передачи, S р ·(S р – 1) вариантов ошибочной трансформации в другие разрешенные комбинации и S р ·(S – S р ) вариантов трансформации в запрещенные комбинации. Р ис. 5.2. Сх ема воз ник нов ени я ошибочная трансформация в запрещенную комбинацию безошибочная передача ошибочная трансформация в разрешенную комбинацию Sр Sр ошибок при передаче кодовых слов. Только передача в запрещенные варианты может быть обнаружена. Доля обнаруживаемых ошибок составляет n k n k р р р р 2 1 2 2 1 S S 1 S S ) S S ( S Обнаруженную ошибку можно исправить, если для каждой запрещенной комбинации можно указать единственную исходную, т.е. посланную комбинацию. Таким образом, ошибка исправляется в S – S р случаях, равных количеству запрещенных комбинаций. Доля исправляемых ошибочных комбинаций от числа обнаруживаемых составляет: k р р р р 2 S 1 ) S S ( S S S Эти две величины характеризуют корректирующую способность кода. Однако на практике следует учитывать не только количество, но и вероятностные характеристики тех или иных ошибочных комбинаций. Определим вероятность ошибочного приема сообщения. Пусть p – вероятность появления ошибки при передаче отдельного бита кодовой комбинации. Для оценки вероятности возникновения ошибки при передаче кодовой комбинации, состоящей их n бит необходимо принять определенные исходные предположения, которые называются математической моделью ошибок. Наиболее простая из них (рассмотрим только ее) – считать появление ошибки в каждом отдельном знаке (бите) кода случайным событием, которое не зависит от того, с ошибками или без них были переданы предыдущие биты. Тогда: 1 – p – вероятность безошибочной передачи отдельного бита; (1 – p) n – вероятность безошибочной передачи цепочки n бит; P n = 1 – (1 – p) n – вероятность появления хотя бы одной ошибки в комбинации n бит. При малых p можно воспользоваться соотношением Бернулли; тогда P n n∙p. Так можно оценить суммарную вероятность появления всех ошибок. Если же требуется найти вероятность ошибки с заданной кратностью t, то следует воспользоваться формулой биноминального распределения: t n t t n n ) p 1 ( p C P Вероятность ошибочной передачи сообщения с учетом всех ошибок кратности от 1 до t находится так: t 1 i i n i i n n ) p 1 ( p C P (1) Связь между корректирующей способностью кода и кодовым расстоянием Важная характеристика помехоустойчивого кода – наименьшее расстояние между разрешенными кодовыми комбинациями d min . Оно обеспечивает корректирующие свойства кода. Определить минимальное кодовое расстояние между разрешенными комбинациями сообщений разведчиков. Ответ: d min = min {6, 5, 5} = 5. Проиллюстрируем этот подход для (3,2)-кода: количество информационных разрядов k = 2, следовательно, число разрешенных кодовых комбинаций S р = 2 2 = 4; общее число кодов S=2 3 =8. Число проверочных бит r = n – k = 1 и устанавливать их значение условимся таким образом, чтобы количество «единиц» во всех кодовых комбинациях было бы четным (по этой причине такой проверочный бит называется битом четности). U i a 1 a 2 b U 1 0 0 0 0 U 2 0 1 1 2 U 3 1 0 1 2 U 4 1 1 0 2 Будем обозначать разрешенные кодовые комбинации U i . Их информационная часть может принимать значения 00, 01,10 и 11 (обозначим эти биты a 1 и a 2 ); проверочный бит b принимает значения, приведенные в таблице. Последняя колонка содержит суммы (количество) бит со значением "1" в каждой кодовой комбинации. Любую из 8 существующих для n = 3 кодовых комбинаций можно считать вектором в пространстве, построенном на единичных векторах a 1 , a 2 , b – это иллюстрируется рисунком 5.3. Отметим разрешенные комбинации ноликами; остальные, очевидно, будут запрещенными - их отметим крестиками. Видно, что минимальное кодовое расстояние между разрешенными комбинациями равно 2 (расстояние между разрешенными вершинами по ребрам куба). На рисунке однократной ошибке соответствует переход из вершины куба в соседнюю вершину. Любая однократная ошибка переводит разрешенную комбинацию в запрещенную, следовательно, может быть обнаружена. Однако исправить такую ошибку нельзя, поскольку в любую из запрещенных вершин за один шаг можно попасть, по крайней мере, из двух разрешенных. Рис. 5.3. К вопросу о связи кодового расстояния и корректирующей способности кода. Обобщим рассуждения. Пусть необходимо построить код, обнаруживающий все ошибки кратности τ и меньше. Построить такой код – это значит из множества S возможных комбинаций выбрать S p разрешенных комбинаций так, чтобы любая сумма по модулю 2 с любым вектором ошибок с весом ω ≤ τ не дала бы в результате никакой другой разрешенной комбинации. Для этого необходимо, чтобы наименьшее кодовое расстояние удовлетворяло условию 1 d min (2) Сможет ли командир обнаружить двукратную ошибку? Ответ: да, потому что 5 ≥ 2+1. Рассмотрим код со значностью n=3. Все возможные комбинации этого кода приведены в таблице: А 1 А 2 А 3 А 4 А 5 А 6 А 7 А 8 000 001 010 011 100 101 110 111 Составим матрицу кодовых расстояний: А 1 А 2 А 3 А 4 А 5 А 6 А 7 А 8 А 1 0 1 1 2 1 2 2 3 А 2 1 0 2 1 2 1 3 2 А 3 1 2 0 1 2 3 1 2 А 4 2 1 1 0 3 2 2 1 А 5 1 2 2 3 0 1 1 2 А 6 2 1 3 2 1 0 2 1 А 7 2 3 1 2 1 2 0 1 А 8 3 2 2 1 2 1 1 0 Для того, чтобы код обеспечивал обнаружение однократных ошибок, необходимо из 8 возможных комбинаций выбрать в качестве разрешенных такие, расстояние между которыми было бы не менее d=2. Например, определим разрешенными комбинациями такие: А 2 = 001, А 3 = 010, А 5 = 100, А 8 = 111. Любая однократная ошибка переводит разрешенную комбинацию в запрещенную. Для обнаружения двукратных ошибок наименьшее кодовое расстояние должно быть d min =3. В качестве примера разрешенных комбинаций в этом случае можно выбрать А 3 =010 и А 6 =101. Пусть теперь необходимо построить код, обеспечивающий исправление однократных ошибок. Выберем в качестве первой разрешенной комбинации А 2 =001. При однократной ошибке комбинация А 2 перейдет в одну из трех комбинаций: А 1 =000, А 4 =011 или А 6 =101 (рис. 5.4). Эти комбинации объявляются запрещенными комбинациями для А 2 . Это означает, что при появлении одной из этих комбинаций на выходе канала связи будет принято решение, что передана комбинация А 2 Рис. Варианты перехода между кодовыми комбинациями при однократной ошибке. Допустим, в качестве второй разрешенной комбинации выбрана А 3 =010, отстоящая на расстоянии d=2. Ей соответствует подмножество запрещенных комбинаций А 4 =011, А 1 =000 и А 7 =110. Однако получилось пересечение подмножеств запрещенных комбинаций. При приеме запрещенных комбинаций А 4 и А 1 нельзя однозначно установить, какая комбинация была послана – А 2 или А 3 . Если же в качестве второй разрешенной комбинации принять А 7 =110, которой соответствуют запрещенные комбинации А 8 =111, А 5 =100 и А 3 =010, то в этом случае подмножества запрещенных комбинаций не пересекаются и имеется однозначное соответствие принятой и переданной комбинации. Следовательно, при d min =3 обеспечивается исправление всех однократных ошибок. В общем случае, для исправления ошибок кратности t минимальное кодовое расстояние должно удовлетворять условию d min ≥ 2t + 1 (3) Сможет ли командир исправить двукратную ошибку? Ответ: да, потому что 5 ≥ 2∙2+1 Аналогично рассуждая, можно установить, что для исправления всех ошибок кратности не более t и одновременного обнаружения всех ошибок кратности не более τ (при τ ≥ t) кодовое расстояние должно удовлетворять условию d min ≥ t + τ + 1 (4) Связь между корректирующей способностью кода и длиной кода Обычная последовательность выбора кода следующая: исходя из мощности M первичного алфавита, определяется количество информационных разрядов; задается возможная кратность ошибок, подлежащих обнаружению и исправлению; определяется количество дополнительных проверочных разрядов, которые вместе с информационными определят длину кода n. А2 А3 А7 А1 А4 А6 А7 А3 А5 А8 d=3 d=2 Пусть известна мощность первичного алфавита М. Необходимое количество информационных битов k log 2 M. Пусть необходимо исправить ошибки кратности от 1 до t. Число возможных однократных ошибок в коде длиной n равно n C 1 n , число двукратных ошибок равно 2 / ) 1 n ( n C 2 n , число возможных t-кратных ошибок равно )! t n ( ! t ! n C t n Общее число ошибок t 1 i i n C E Эти Е ошибок могут проявиться в каждой из 2 k возможных входных последовательностей. Полное число ошибочных комбинаций, подлежащих исправлению, равно Е∙2 k . Код длиной n обеспечивает исправление не более 2 n - 2 k комбинаций, так как именно столько запрещенных комбинаций. Следовательно, необходимое условие для возможности исправления ошибок можно записать в виде Е∙2 k ≤ 2 n - 2 k Отсюда получим: E 1 2 2 k n Обозначив буквой r число проверочных символов, и учитывая, что r = n – k, получим: t 1 i i n r C 1 2 Учитывая, что 0 n С 1 , можно записать t 0 i i n r C 2 или t 0 i i n 2 C log r Это так называемая граница Р.Хемминга (или условие Хемминга), связывает число проверочных бит и значность кода. В частном случае, когда требуется исправить однократные ошибки, имеем зависимость 2 r – r – 1 ≥ k. Оценить количество проверочных символов и избыточность кода можно из таблицы, построенной по указанной зависимости: r 2 3 4 5 6 7 8 9 10 k 1 4 11 26 57 120 247 502 1013 F 0,67 0,43 0,27 0,16 0,10 0,06 0,03 0,02 0,01 Вспомнить вторую теорему Шеннона. Действительно, теоретически, увеличивая длину блока можно бесконечно уменьшать избыточность, обеспечивая вместе с тем помехоустойчивость кода. Сравните с аналогичной таблицей для помехоустойчивого кода, исправляющего двукратные ошибки r 2 3 4 5 6 7 8 9 10 11 12 13 k 1 1 2 3 5 9 15 23 35 53 79 115 F 0,67 0,75 0,67 0,63 0,55 0,44 0,35 0,28 0,22 0,17 0,13 0,10 Выполняется ли неравенство Хемминга в задаче о разведчиках?? Ответ: да, но только с учетом 2-кратных ошибок. Если же требуется исправлять и однократные ошибки, то r≥log 2 (1+8+28)=6 Контрольные вопросы 1. Назовите два типа помех, приводящих к ошибкам в передаваемой информации . 2. Какой тип помех представляет наибольшую опасность для ИВС и почему? 3. В какой части спектра сосредоточена основная энергия импульса напряжения? 4. Перечислите источники внешних помех передаче информации. 5. Что понимается под помехоустойчивостью АПД и каналов? 6. Назовите три способа повышения верности передаваемой информации с помощью устройств зашиты информации (УЗО). Какой из них обладает большей эффективностью? 7. Какие коды называются помехоустойчивыми? 8. Какими методами может быть организован обмен с квитированием? Сравните эти методы. 9. Поясните, в чем заключается контроль информации по приоритету. 10. Как осуществляется циклический избыточный контроль передаваемой информации? 11. От какого параметра зависит корректирующая способность кода? 12. Что называется коэффициентом избыточности кода? 13. Назовите три типа обнаруживающих кодов. 14. Какова обнаруживающая способность итеративного кода? 15. Каковы корректирующая и обнаруживающая способности кода Хэмминга? 16. Назовите основную операцию, выполняемую в кодирующих и декодирующих устройствах кода Хэмминга. Выполнить вопросы и упражнения 1. Выбрать способ защиты от ошибок, обеспечивающий вероятность побайтовой передачи Рхх<1*10-6 при передаче данных по симплексному двухпроводному телефонному каналу связи со скоростью 1200 бит/с при условии, что ошибки на выходе дискретного канала группируются в пакеты длиной не более 12 бит, а минимальный интервал между пакетами составляет 3 с. Кодирование должно обеспечить вероятность ошибки по элементам на выходе дискретного канала Р 0 не более 1*10 -4 2. Построить таблицу кода Хемминга для семиразрядного слова. |