Самосинхронизирующиеся коды

Коды, дозволяющие выделять синхросигнал из последовательности состояний полосы, именуются самосинхронизирующимися. При использовании таких кодов отпадает необходимость в отдельной синхронизации передатчика и приемника.

Одна из вероятных реализаций самосинхронизирующих кодов – двухфазные коды, в каждом битовом интервале которых непременно находится переход из 1-го состояния в другое.

Большая часть технологий локальных сетей употребляют конкретно самосинхронизирующие Самосинхронизирующиеся коды коды: в Ethernet применяется манчестерский код, в Token Ring – вариант дифференциального манчестерского кода


КОНТРОЛЬ ПЕРЕДАЧИ Инфы И СЖАТИЕ ДАННЫХ

Самовосстанавливающиеся коды

Одним из средств борьбы с помехами являются самовосстанавливающиеся (корректирующие) коды, дозволяющие не только лишь найти, да и поправить ошибки при приеме.

Пусть употребляется n-разрядный двоичный код. Ошибка при Самосинхронизирующиеся коды приеме кодовой композиции заключается в том, что (под воздействием помехи) или переданный нуль был принят, как единица, или единица была принята, как нуль. Если в кодовой композиции ошибка находится исключительно в одном разряде, то такую ошибку будем именовать одиночной, если в 2-ух разрядах – двойной и т.д.

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

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

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

Периодические коды

Другой подход к построению кодов – разделение разрядов кода на информационные и контрольные. Такие коды именуются периодическими. Пусть всего в коде n разрядов, из их k – информационных и r – контрольных разрядов (n=k+r). Таковой код может передавать N = 2k разных сообщений. Из Самосинхронизирующиеся коды r контрольных разрядов можно организовать 2r разных композиций. Для обнаружения и исправления одиночной ошибки необходимо, во-1-х, указать наличие/отсутствие ошибки и, во-2-х, указать номер разряда, в каком произошла ошибка.

Таким макаром, чтоб в контрольных разрядах можно было передавать информацию для исправления одиночных ошибок, их количество Самосинхронизирующиеся коды должно удовлетворять неравенству 2r≥n+1 либо 2n/(n+1) ≥N. Если достигается равенство: 2n/(n+1) = N, то количество контрольных разрядов, приходящихся на один информационный, будет минимальным. К примеру, для N=4 разных сообщений (k=2) меньшее значение n равно 5 (24/(4+1) = 3,2 < 4, а 25/6 ≈ 5,3 > 4). Означает, количество контрольных разрядов, нужное для обнаружения и исправления одиночных ошибок r = n-k = 5-2 = 3.

Методы Самосинхронизирующиеся коды сжатия данных

В общем смысле под сжатием данных понимают такое их преобразование, что его итог занимает наименьший объем памяти. При всем этом (по сопоставлению с начальным представлением) экономится память для их хранения и сокращается время передачи сжатых данных по каналам связи. Синонимы термина “сжатие” – упаковка, компрессия, архивация. Оборотный процесс (получение Самосинхронизирующиеся коды начальных данных по сжатым) именуется распаковкой, декомпрессией, восстановлением.

Качество сжатия характеризуется коэффициентом сжатия, равным отношению объема сжатых данных к объему начальных данных.

Зависимо от вероятной точности восстановления начальных данных, различаю сжатие без утрат (данные восстанавливаются точно в начальном виде) и сжатие с потерями (восстановленные данные не схожи Самосинхронизирующиеся коды начальным, но их различиями в том контексте, в каком эти данные употребляются, можно пренебречь). Сжатие с потерями применяется, к примеру, для упаковки разноцветных фотографических изображений (метод JPEG), звука (метод MP3), видео (группа алгоритмов MPEG). При всем этом употребляются особенности людского восприятия: к примеру, глаз человека не может различить два близких колера цвета Самосинхронизирующиеся коды, закодированных 24 битами, потому можно без видимых искажений уменьшить разрядность представления цвета.

Для многих разновидностей данных – текстов, исполняемых файлов и т.д. – допустимо применение только алгоритмов сжатия без утрат.

Сжатие без утрат, в главном, базируется на 2-ух группах способов: словарных и статистических. Словарные способы употребляют наличие повторяемых групп данных и Самосинхронизирующиеся коды, к примеру, записывают 1-ое вхождение повторяемого участка конкретно, а все следующие вхождения подменяют на ссылку на 1-ое вхождение. Другие словарные способы раздельно хранят словарь в очевидной форме и подменяют все вхождения словарных определений на их номер в словаре.

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

Метод RLE

Самый обычной из словарных способов – RLE (Run Length Encoding, кодирование переменной длины) умеет сжимать данные, в каких Самосинхронизирующиеся коды есть последовательности циклических байтов. Упакованные RLE данные состоят из управляющих байтов, за которыми следуют байты данных. Если старший бит управляющего б равен 0, то последующие байты (в количестве, записанном в 7 младших битах управляющего б) при упаковке не изменялись. Если старший бит равен 1, то последующий б необходимо повторить столько раз, какое Самосинхронизирующиеся коды число записано в других разрядах управляющего б.

К примеру, начальная последовательность

00000000 00000000 00000000 00000000 11001100 10111111 10111011

будет закодирована в последующем виде (выделены управляющие байты):

1000010000000000 00000011 11001100 10111111 10111011.

А, к примеру, данные, состоящие из сорока нулевых байтов, будут закодированы всего 2-мя б: 1010 100000000000.

Метод Лемпела-Зива

Более обширно употребляются словарные методы из семейства LZ, чья мысль была описана Лемпелом и Самосинхронизирующиеся коды Зивом в 1977 году. Существует огромное количество модификаций этого метода, отличающихся методами хранения словаря, прибавления слова в словарь и поиска слова в словаре.

Словом в этом методе именуется последовательность знаков (не непременно совпадающая со словом естественного языка). Слова хранятся в словаре, а их вхождения в начальные данные заменяются адресами (номерами) слов в словаре Самосинхронизирующиеся коды. Некие разновидности метода хранят раздельно словарь и раздельно упакованные данные в виде последовательности номеров слов. Другие считают словарем весь уже скопленный итог сжатия. К примеру, сжатый файл может состоять из записей вида [a,l,t], где a – адресок (номер позиции), с которой начинается такая же строчка Самосинхронизирующиеся коды длины l, что и текущая строчка. Если a>0, то запись считается ссылкой на словарь и поле t (текст) в ней – пустое. Если a = 0, то в поле t записаны l знаков, которые до сего времени в таковой последовательности не встречались.

Метод сжатия заключается в неизменном поиске в уже упакованной части данных Самосинхронизирующиеся коды наибольшей последовательности знаков, совпадающей с последовательностью, начинающейся с текущей позиции. Если такая последовательность (длины > 3) найдена, в итог записывается ее адресок и длина. По другому в итог записывается 0, длина последовательности и сама (несжатая) последовательность.


samogipnoz-referat.html
samohodnaya-issledovatelskaya-stanciya-na-osnove-platformi-beagleboard.html
samoindukciya-energiya-magnitnogo-polya.html