Сети и телекоммуникации (заочное обучение, бакалавриат)

С необходимостью кодирования данных впервые столкнулись более полутораста лет назад, вскоре после изобретения телеграфа. Каналы были дороги и ненадежны, что сделало актуальной задачу минимизации стоимости и повышения надежности передачи телеграмм. Проблема еще более обострилась в связи с прокладкой трансатлантических кабелей. С 1845 года вошли в употребление специальные кодовые книги; с их помощью телеграфисты вручную выполняли «компрессию» сообщений, заменяя распространенные последовательности слов более короткими кодами. Тогда же для проверки правильности передачи стали использовать контроль четности, метод, который применялся для проверки правильности ввода перфокарт еще и в компьютерах первого и второго поколений. Для этого во вводимую колоду последней вкладывали специально подготовленную карту с контрольной суммой. Если устройство ввода было не слишком надежным (или колода — слишком большой), то могла возникнуть ошибка. Чтобы исправить ее, процедуру ввода повторяли до тех пор, пока подсчитанная контрольная сумма не совпадала с суммой, сохраненной на карте. Мало того, что эта схема неудобна, она к тому же пропускает двойные ошибки. С развитием каналов связи потребовался более эффективный механизм контроля.

Первым теоретическое решение проблемы передачи данных по зашумленным каналам предложил Клод Шеннон, основоположник статистической теории информации. Шеннон был звездой своего времени, он входил в академическую элиту США. Будучи аспирантом Ванневара Буша, в 1940 году он получил премию имени Нобеля (не путать с Нобелевской премией!), присуждаемую ученым, не достигшим 30 лет. Работая в Bell Labs, Шеннон написал работу «Математическая теория передачи сообщений» (1948), где показал, что если пропускная способность канала выше энтропии источника сообщений, то сообщение можно закодировать так, что оно будет передано без излишних задержек. Это умозаключение содержится в одной из доказанных Шенноном теорем, ее смысл сводится к тому, что при наличии канала с достаточной пропускной способностью сообщение может быть передано с некоторыми временными задержками. Кроме того, он показал теоретическую возможность достоверной передачи при наличии шума в канале. Формулу C = W log ((P+N)/N), высеченную на скромном памятнике Шеннону, установленном в его родном городе в штате Мичиган, сравнивают по значению с формулой Альберта Эйнштейна E = mc².

Труды Шеннона дали пищу для множества дальнейших исследований в области теории информации, но практического инженерного приложения они не имели. Переход от теории к практике стал возможен благодаря усилиям Ричарда Хэмминга, коллеги Шеннона по Bell Labs, получившего известность за открытие класса кодов, которые так и стали называть «кодами Хэмминга». Существует легенда, что к изобретению своих кодов Хэмминга подтолкнуло неудобство в работе с перфокартами на релейной счетной машине Bell Model V в середине 40-х годов. Ему давали время для работы на машине в выходные дни, когда не было операторов, и ему самому приходилось возиться с вводом. Как бы то ни было, но Хэмминг предложил коды, способные корректировать ошибки в каналах связи, в том числе и в магистралях передачи данных в компьютерах, прежде всего между процессором и памятью. Коды Хэмминга стали свидетельством того, как можно практически реализовать возможности, на которые указывают теоремы Шеннона.

Хэмминг опубликовал свою статью в 1950 году, хотя во внутренних отчетах его теория кодирования датируется 1947 годом. Поэтому некоторые считают, что отцом теории кодирования следует считать Хэмминга, а не Шеннона. Впрочем, в истории техники бесполезно искать первого.

Достоверно только то, что именно Хэмминг первым предложил «коды с исправлением ошибок» (Error-Correcting Code, ECC). Современные модификации этих кодов используются во всех системах хранения данных и для обмена между процессором и оперативной памятью. Один из их вариантов, коды Рида-Соломона применяются в компакт-дисках, позволяя воспроизводить записи без скрипов и шумов, которые могли бы вызвать царапины и пылинки. Существует множество версий кодов, построенных «по мотивам» Хэмминга, они различаются алгоритмами кодирования и количеством проверочных битов. Особое значение подобные коды приобрели в связи с развитием дальней космической связи с межпланетными станциями, например, существуют коды Рида-Мюллера, где на семь информационных битов приходится 32 контрольных, или на шесть — 26.

Среди новейших кодов ECC следует назвать коды LDPC (Low-Density Parity-check Code). Вообще-то они известны лет тридцать, но особый интерес к ним обнаружился именно в последние годы, когда стало развиваться телевидение высокой четкости. Коды LDPC не обладают 100-процентной достоверностью, но вероятность ошибки может быть доведена до желаемой, и при этом с максимальной полнотой используется пропускная способность канала. К ним близки «турбокоды» (Turbo Code), они эффективны при работе с объектами, находящимися в условиях далекого космоса и ограниченной пропускной способности канала.

В историю теории кодирования прочно вписано имя Владимира Александровича Котельникова. В 1933 году в «Материалах по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи» он опубликовал работу «О пропускной способности ?эфира? и ?проволоки?». Имя Котельникова на правах равного входит в название одной из важнейших теорем теории кодирования. Этой теоремой определяются условия, при которых переданный сигнал может быть восстановлен без потери информации.

Эту теорему называют по-разному, в том числе «теоремой WKS» (аббревиатура WKS взята от Whittaker, Kotelnikov, Shannon). В некоторых источниках используют и Nyquist-Shannon sampling theorem, и Whittaker-Shannon sampling theorem, а в отечественных вузовских учебниках чаще всего встречается просто «теорема Котельникова». На самом же деле теорема имеет более долгую историю. Ее первую часть в 1897 году доказал французский математик Эмиль Борель. Свой вклад в 1915 году внес Эдмунд Уиттекер. В 1920 году японец Кинносуки Огура опубликовал поправки к исследованиям Уиттекера, а в 1928 году американец Гарри Найквист уточнил принципы оцифровки и восстановления аналогового сигнала. 

Теперь, когда мы выяснили причины и правила корректировки потери и искажения сигналов, перейдем к стандарту кодирования передачи информации.

Предварительно договоримся, что каждому символу мы сопоставим определённое число, 

а затем будем передавать  представление этого числа в двоичной форме при помощи электрических импульсов.

На выходе из приёмника у нас получится вот такой вот график напряжения:

еперь осталось просто взять и расшифровать этот сигнал на приёмнике. Включив передачу, мы обнаружили, что реальный мир быстро разрушил наши теоретические построения. Приёмник получил вовсе не то, что мы ожидали:

Оказалось, что на приёмное устройство включилось несколько позднее передающего, а кроме того, генераторы тактовой частоты у приёмника и передатчика несколько различаются. Хоть на них и написано 100 МГц, выяснилось, что приёмник работает с частотой 101,3 МГц, а передатчик – с частотой 100,9 МГц. 

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

Закодируем сигнал, разделив каждый такт на 2 части.  Ноль мы кодируем падением потенциала, а единицу – ростом:

Таким образом нам удалось передать короткое сообщение с одного компьютера на другой а заодно мы заново изобрели "Манчестерское кодирование". Название кодирования происходит из университета Манчестера, где такое кодирование было впервые использовано для хранения данных на магнитном барабане компьютера Манчестерский Марк I.

Если вы зачистите пару проводов в сетевом кабеле и подключите их к осциллографу, вы увидите на экране картинку, очень похожую на эту:

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

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

Нам нужен какой-то способ разделять разные блоки данных между собой, назовём их кадры (или фрейм, frame) чтобы приёмник мог точно знать, где заканчивается один пакет, и начинается другой. Поскольку всё, что мы можем передавать – это нули и единицы, договоримся о специальном символе-разделителе, например, такой последовательности: 01111110. Теперь, перед началом пакета мы всегда будем посылать эту последовательность, а приёмник будет знать, что получает новый кадр. Тут возникает вопрос, а как поступить, если в передаваемых данных так же встретится подобная комбинация бит? Давайте тогда договоримся, что если внутри кадра нам требуется передать более 5 последовательных единиц подряд, то вместо 111111 мы будем передавать 1111101 – то есть, вставлять нолик после каждых 5 единиц. Приёмник, с другой стороны, так же будет настроен на то, чтобы игнорировать этот ноль. Чтобы не терять синхронизацию, во время простоя приёмник будет постоянно передавать последовательность-разделитель во время установленного соединения.

Когда же требуется установить новое соединение и установить синхронизацию по частоте будем пользоваться следующим соглашением – сначала несколько наносекунд молчания, длительность должна соответствовать как минимум длительности передачи 96 бит (12 блоков по 8 бит или октетов). Это нужно для того, чтобы точно удостовериться, что данные в настоящий момент не передаются. Затем будет посылаться преамбула – 56 бит повторяющихся пар нулей и единиц: 10101010101010101010101010101010101010101010101010101010 – так приёмник сможет точно измерить длительность, с которой будут передаваться биты. Затем мы передадим уже знакомую последовательность начал кадра: 01111110, после чего – наше сообщение.

Мы более-менее успешно справлялись только с одним видом соединения – от одной точки к другой (или по-английски Point-to-Point). А соглашение и правила, по которым мы условились осуществлять передачу, давайте назовём ПРОТОКОЛ. Но тут мы решили организовать компьютерную сеть, состоящую из нескольких компьютеров. Можно, конечно, оснастить каждую пару компьютеров отдельным каналом связи, но проще будет подумать, какие необходимо внести изменения в наш протокол, чтобы можно было бы передавать сообщение по одному физическому каналу на любой из подключённых к нему приёмников.

Для начала необходимо как-то идентифицировать компьютеры в нашей сети. К счастью, каждое приёмо-передающее устройство имеет нечто вроде уникального 6-значного (48 бит) серийного номера, который обычно записывается в шестнадцатеричном виде через двоеточие, например e0:62:0f:1a:02:2d, иначе он называется MAC-адрес (от Media Access Control – управление доступом к среде).

То есть внутри нашего кадра мы теперь будем сначала передавать MAC-адрес приёмного устройства на компьютере-получателе, затем свой адрес (чтобы нам могли ответить), затем укажем подсказку, какие данные внутри, затем – сами данные, после чего – их контрольную сумму (её посчитаем по алгоритму CRC-32).

Наш кадр (Ethernet frame) приобретает следующий вид:

Ура, мы заново изобрели протокол Ethernet, одну из разновидностей протокола HLDC (High-Level Data Link Control).

Что передать в качестве типа данных? Давайте пока передадим 0001000 00000000 (0x800), а потом к этому вернёмся.

Тут стоит сказать, что есть одна разновидность HLDC под названием Point-to-Point protocol или сокращённо PPP, которая чуть отличается от вышеприведённой схемы. Поскольку, как следует из названия, он используется для связи вида «точка-к-точке», в поле адрес получателя всегда вносится 11111111 (FF), а в адрес получателя – всегда 00000011 (3). Почему? Так повелось исторически.