Кодирование сигнала

Продолжаем разговор про технологии беспроводной связи. На предыдущих занятиях мы разобрали процесс передачи данных с физической точки зрения. Мы увидели, что основным носителем передачи информации является именно бит. Поэтому в нашем треке мы уделяем этой теме достаточно серьезное внимание. 

Сегодня речь пойдет о непосредственном кодировании сигнала. Мы видели, что присутствие шума, сторонних помех приводит к тому, что принятый сигнал искажается. Он уже не такой, какой был на выходе передатчика. На входе приемника сигнал уже испытал все прелести канала связи и приобрел какие-то дополнительные ошибки. 

Например, давайте рассмотрим, как же выглядит в битовом представлении символ 0. Символ 0 в таблице ASCII имеет номер 48. На 0 в данном случае выделяется один байт - 8 бит. 48 в двоичном представлении это 32+16, то есть это 00110000. 

Когда передается наш символ 0, на самом деле передаются эти самые 8 бит и при передаче информации шум или помехи могу воздействовать на любой из этих битов или на группу битиков. В итоге мы получим на входе приемника не обязательно символ 0 или символ 1. Мы можем получить 9 вариантов принятого сигнала при условии, что ошибка допущена и в одном бите. 

Например, на этом рисунке вы видите таблицу, в которой представлены всевозможные варианты принятого сигнала в битовом представлении и соответствующие им символы. Вы видите, что у нас всего 9 вариантов: 8 вариантов с ошибкой, 1 вариант правильный. 

Как можно было бы бороться с шумами? Мы уже говорили, что можно увеличивать мощность передаваемого сигнала, тогда надежность в этом смысле будет выше, но этого же захотят наши соседи. Они тоже захотят увеличить мощность передаваемого сигнала. Когда все вокруг начнут увеличивать мощность передаваемого сигнала, тогда соответственно будут и мешать друг другу сильнее. Кроме того, вопрос усиления мощности сигнала - это дополнительные расходы энергии и дополнительные требования к аппаратуре. С медицинской точки зрения, электромагнитного фона, экологии - это тоже критичный вопрос. Поэтому, конечно, все бы хотели остаться на приемлемом уровне излученной мощности, но при этом найти инструмент, технологию, которая бы позволила вам каким-то образом находить ошибки, а ещё лучше их исправлять. 

Самый простой и распространенный способ, с помощью которого можно показать как можно обнаружить ошибку, это так называемая контрольная сумма. Вы к вашему информационному сигналу можете добавить еще один контрольный символ, например, последний, который может принимать значение, либо 0, либо 1, но так, чтобы сумма битов по модулю 2 была равна нулю. Так действует контрольная сумма, и так достаточно часто поступают, когда хотят найти быстрое оптимальное решение, позволяющее диагностировать наличие одной ошибки. 

Но отсюда видно, что если у вас будет не одна ошибка, а две, то есть четное количество, то ваш контрольный битик уже не сможет эту ситуацию распознать. Три, пять, одну ошибку - да, а четное уже нет. Кроме того, используя 1 контрольный бит в конце как метод диагностики ошибок, позволит вам только понять есть ошибка или нет ошибки. А исправить и найти ее в данном случае, конечно, не представляется возможным. Поиском решений того, как, каким же образом можно добавить такие контрольные биты в наш сигнал с тем, чтобы можно было обнаружить ошибку, как раз занимается такая наука как теория кодирования. 

Теория кодирования - очень интересное направление, которое находится на стыке математики, информатики. Как мы видели здесь, можно подойти и с точки зрения физики. 

Мы рассмотрим простой вариант помехоустойчивого кода, позволяющего обнаруживать и исправлять однократную ошибку и при этом обнаруживать двукратную ошибку. Код Хэмминга был разработан уже более 70 лет назад, но он до сих пор используется в каких-то простых технологиях, ввиду своей наглядности и простоты реализации. Этот код, в смысле методического шага, в понимании, как работают помехоустойчивые коды, очень интересен и полезен. 

Давайте, особо не погружаясь в теорию помехоустойчивых кодов, разберемся как работает помехоустойчивый код Хэмминга. Это в дальнейшем поможет подойти к теории помехоустойчивых кодов уже с каким-то пониманием как конкретно работает реализация кода, допустим Хэмминга.

 Посмотрим, что лежит в основе этого кода. Код интересен тем, что эта технология с контрольной суммой, про которую мы начали говорить, использована очень грамотно и красиво в этом коде.  Прежде чем переходить к нему, надо отметить очень важное обстоятельство, что этот код блочный, то есть у вас блок передаваемых данных разбивается на равные блоки какой-то длины а также он циклический, двоичный, то есть в этом смысле он работает с информацией представленной в виде 0 и 1, то есть двоичной системе. А что мы знаем про двоичную систему? Мы в принципе можем любое число разложить в двоичную систему. 

Например, давайте обратимся к началу. Вот наш 0, вот его представление в двоичной системе. Что можно сказать? Посмотрите, возвращаясь к началу к первому слайду, мы видим, что у нас есть 9 вариантов того, как приемник может принять сигнал. 9 вариантов: один без изменений и 8 вариантов с однократной ошибкой

Для того, чтобы пронумеровать все 9 вариантов, нужно как минимум 4 бита, то есть нам как минимум нужно 4 контрольные суммы для того, чтобы все возможные варианты предусмотреть. Почему? Потому что 2^3=8, еще не 9, а 2^4=16 и уже больше 9. Поэтому нам нужно 2^4, но тогда получается некоторая избыточность. 

Поэтому давайте мы попробуем посмотреть на эту ситуацию так:  попробуем посмотреть на 7-битную последовательность, то есть уменьшим на исходную последовательность на 1 бит. 

То есть сейчас будем рассматривать не 8 бит, а 7 бит. В этом случае у нас уже 8 вариантов того, как может выглядеть принятый сигнал. 8 вариантов, 2^3. Следовательно для того, чтобы описать все возможные состояния нам нужно 3 контрольных бита. Таким образом, из 7 бит, которые мы собираемся передавать, 3 надо отвести на контрольные, а соответственно 4 - на информационные. 

Теперь если мы вернемся к нашему 0 и увидим здесь его двоичное представление, мы видим 8 бит. Мы видим 2 половинки по 4 бита в каждой, которую мы будем передавать по отдельности. Каждая половина содержит информационные биты по 4 штуки, следовательно из предыдущего понято, что нужно к каждой половинке добавить еще 3 контрольных бита. 

А теперь давайте подумаем, как эти контрольные биты должны быть добавлены. Вот здесь код Хэмминга показывает насколько красиво он устроен внутри. Разберемся, как он умудрился быть таким красиво устроенным внутри. 

У нас вместе с информационными и контрольными битами в сумме - 7 бит. Давайте теперь для каждого бита представим его номер позиции в двоичном представлении: первый, второй, третий, четвертый, пятый, шестой, седьмой. Соответственно, первый-001, второй-010, третий-011 и тд. 

Теперь нужно придумать какие-то хитрые контрольные суммы. Нам нужно подумать, где логичнее всего поставить наши контрольные биты, но так, чтобы контрольный бит в каждой сумме участвовал единожды. На то он и контрольный. То есть наш контрольный бит должен контролировать какую-то часть последовательности, и понятно, что два контрольных бита в этой последовательности участвовать не могут. Зачем такая избыточность, мы сейчас контролируем одну ошибку. 

А теперь внимательно посмотрим на двоичное представление номеров бит. Давайте сделаем вот что: пусть первый контрольный бит контролирует первый разряд позиций двоичных представлений, какие это позиции? Соответственно, это нечетные позиции, первый, третий, пятый, седьмой номер, то есть это номера на конце которых висит единичка. 

Итак, мы контролируем первую позицию, то есть первый контрольный бит должен содержать сумму по модулю два значений этих позиций. 

Теперь посмотрим дальше, второй битик содержит разложение 010, и так мы видим, что у него единичка стоит на втором месте. Давайте теперь найдем все такие позиции, у которых единичка стоит на втором месте.

Это сама двойка, тройка, шестерка 4+2, и семерка 4+3, то есть контрольная сумма, второго контрольного бита будет у нас содержать сумму по модулю два, второго, третьего, шестого, седьмого бита. 

Теперь посмотрим на последний разряд - третий. Будем действовать по аналогии, с какой позиции заполняется третий разряд? С четверки, четверка - это 100, а также этот символ находится у пятерки, шестерки, семерки. Таким образом, мы выписали контрольные суммы для каждого разряда, для каждого разряда тех номеров, которые нумеруют наши биты. 

Теперь из этой последовательности легко увидеть, что для того, чтобы контрольные биты участвовали в каждой конкретной сумме один раз, каждый контрольный бит, должен в каждой из этих трех сумм участвовать один раз. У нас три контрольные суммы, 3 контрольных бита.

Отсюда логично предположить, что если эти контрольные биты будут находиться в позициях, соответствующих степеням двойки, то есть 1:  2^0, 2: 2^1, 4: 2^2, то фактически, это номера бит с которых мы стартуем контрольной суммой. И видно, что если мы контрольные суммы расположим в позициях 1, 2 и 4, то они однократно будут участвовать в каждой сумме, прекрасно. Таким образом, мы увидели, как можно найти контрольные биты, которые позволяют закодировать сигнал. 

Если взять наш 0, то первые 4 нуля, исходя из данного представления, дополнятся еще тремя 0-ми, то есть вместо 4-х их станет 3. А если взять старшую половинку битов, то она превратиться в соответствии с данной двоичной арифметикой в 0111, то есть не 2 единички на конце, а три. Таким образом, в  соответствии с тем, что мы сказали, 4 нуля превращаются в 7 нулей и старшие пол бита превращаются в следующее представление вы видите его на слайде.

Обратите внимание, что у нас есть отличный инструмент для того, чтобы находить контрольную сумму, и отличная идея, которая подсказывает, как это делать. Даже если вы забыли, но будете это помнить, то исходя из принципа, легко восстановите в памяти, как работает код Хэмминга. 

Кроме того, давайте еще подумаем о том, что у нас информационных 4, это 16 вариантов, а всего 7, это 128 вариантов, соответственно разрешенных вариантов в 8 раз меньше, чем всего возможных. Это логичное следствие того, что мы собираемся обнаруживать однократную ошибку. Наши разрешенные последовательности кодовых слов должны отличаться друг от друга в трех битах, это позволяет вам не перепутать их.

Данную тему мы продолжим, обязательно поговорим про расстояние Хэмминга. Сегодня рассмотрим эту  красивую идею с контрольными символами в коде Хэмминга, а на следующих занятиях больше погрузимся в теорию.

У нас есть закодированная последовательность и есть шумы, которые могут исказить ее. Допустим искажается 7-ой бит, вместо 0 появилась 1. Код то у нас помехоустойчивый, сейчас мы попробуем эту ошибку обнаружить и исправить. Действуя с той же логикой, с которой кодировали, давайте попробуем и декодировать. Это означает, что сначала мы найдем контрольную сумму 1-го, 3-го, 5-го и 7-го бита. Это те номера, в двоичном разложении которых на конце сидит 1. Обратите внимание, что сумма по модулю два у вас дает 1. Это означает, что в этой контрольной сумме есть ошибка, ведь должен же быть 0. 

Рассмотрим следующую контрольную сумму 2, 3, 6, 7. Опять 1, и в этом разряде есть ошибка. 

И последняя контрольная сумма 4, 5, 6, 7. И в этом разряде ошибка, значит в двоичном представление позиция, на которой находится ошибка и в 1-ом, и во 2-ом, и в 3-ем разряде, соответственно суммируя все эти позиции, получаем семерку. 

Если мы посмотрим на последовательность 111, то фактически мы нашли синдром. Так называется контрольная сумма при декодировании. Мы ищем синдром. Синдром помогает нам определить позицию, в которой произошла ошибка.  Итак, мы видим, что позиция в которой произошла ошибка - 7. Мы ее там допустили, мы сейчас проверяем нашу логику, код Хэмминга работает. Если мы понимаем, как кодировать, то понимаем, как декодировать. Сама логика подсказывает как это делать. 

Код Хэмминга - блочный. Сейчас мы работали в предположении, что у нас возникает однократная ошибка в 7 битах. Не двукратная, не трехкратная, а однократная ошибка в 7 битах. Давайте на секундочку задумаемся, что будет, если мы будем кодировать кодом Хэмминга (7, 4), а шум в среднем будет давать одну ошибку на 8 бит. В этом случае шум более редкий. 

Мы предполагали, что одна ошибка может возникать в течение 7 бит, а в данном случае ошибка возникает в течение 8 бит. Казалось бы, в этом случае мы должны всегда исправлять ошибку. Но давайте посмотрим, как работает блочный код. Мы уже говорили, что информация разбивается на блоки, и мы отдельно передаем 7 бит, потом еще 7 бит и тд. 

Посмотрим на данный рисунок: 7 бит рядом, еще 7 бит, а ошибка возникает каждые 8 бит. А что будет, например, если ошибка возникла в конце 8-битной последовательности, то есть на 8ом месте? Эта ошибка попадает во второй 7-битный блок, и дальше начинается второй 8-битный блок. Блок с первой 7-битной позиции, и допустим, ошибка возникла во втором 8-битном блоке. А это привело к тому, что у нас возникает двукратная ошибка в 7-битном блоке. 

Давайте оценим вероятность этой ошибки. Допустим, шум равномерный. 
Как видно из рисунка,  это (⅛) *(6/8)=6/64 
Это примерно 10%. 

Блочные коды интересные, красивые, но нужно очень хорошо знать, как устроен шум для того, чтобы иметь представление о том, как в ваших последовательных блоках могут возникать ошибки. 

Для размышления

1. Переведите числа 156, 291 из десятичной системы счисления в двоичную.
2. Переведите числа 1000110; 10111010,101 из двоичной системы счисления в десятичную.

Материалы

• Таблица ASCII
• Радиотехнические системы передачи информации. А. С. Садомовский, С. В. Воронов (главы с 6.1 по 6.3 включительно)