Избыточное кодирование код рида соломона. Код Рида — Соломона. Реализация кодировщика и декодера Рида-Соломона. Аппаратная реализация

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

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

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

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

Так что же значит понятие "я нахожусь в сети"? Вот у меня есть смартфон, подключенный к интернет постоянно. Он постоянно со мной и через него я могу получить сообщения от людей из интернет даже если я сам им не пользуюсь. Я могу водить машину, сидеть в кафе, в библиотеке или в кинотеатре имея при себе этот смартфон. Так вот скажите, нахожусь-ли я в сети в этот момент? Ответ прост - смартфон находится в сети, а я занимаюсь другими делами, но у меня есть возможность связи с людьми через интернет, даже если я не сижу и не смотрю безотрывно в экран. Да, впрочем, я точно также все время доступен и для телефонного звонка, если кому-то захочется поговорить, но только номер своего телефона я не буду сообщать тем, с кем не желаю разговаривать. И в интернете я имею возможность не сообщать другим людям свои контактные данные, оставаясь доступным для друзей.

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

Введение

TCPView - это программа, предназначенная для операционной системы Windows, которая выводит на экран списки конечных точек всех установленных в системе соединений по протоколам TCP и UDP с подробными данными, в том числе с указанием локальных и удаленных адресов и состояния TCP-соединений. В операционных системах Windows NT, 2000 и XP программа TCPView также сообщает имя процесса, которому принадлежит конечная точка. Программа TCPView является дополнением программы Netstat, поставляемой вместе с ОС Windows, и предоставляет расширенный набор сведений в более удобной форме. В комплект загрузки программы TCPView входит программа Tcpvcon с теми же функциональными возможностями, предназначенная для работы в режиме командной строки.

Программа TCPView работает в операционных системах Windows NT/2000/XP и Windows 98/Me. Программу TCPView можно использовать также в операционной системе Windows 95 при условии установки пакета обновления Winsock 2 для ОС Windows 95, предоставляемого корпорацией Microsoft.

Использование программы TCPView

При запуске программа TCPView формирует список всех активных конечных точек соединений по протоколам TCP и UDP, отображая все IP-адреса в виде доменных имен. Чтобы переключить режим отображения для просмотра адресов в цифровом виде, можно использовать кнопку панели инструментов или пункт меню. В операционных системах Windows XP программа TCPView для каждой конечной точки отображает имя процесса, которому эта точка принадлежит.

По умолчанию программа TCPView обновляет информацию один раз в секунду, но период обновления можно изменить с помощью пункта Refresh Rate (Период обновления) в меню Options (Параметры). Если в период между обновлениями состояние конечной точки изменилось, она выделяется желтым цветом, если конечная точка удалена - красным цветом, новые конечные точки отображаются зеленым цветом.

Чтобы закрыть установленные подключения по протоколам TCP/IP (с отметкой состояния ESTABLISHED (установлено)), можно выбрать пункт Close Connections (Закрыть подключения) в меню File (Файл) или щелкнуть правой кнопкой мыши какое-либо подключение и выбрать в контекстном меню пункт Close Connections .

Данные, отображенные в окне программы TCPView, можно сохранить в виде файла с помощью пункта меню Save (сохранить).

Применение программы Tcpvcon

Применение программы Tcpvcon аналогично применению служебной программы netstat, которая встроена в операционную систему Windows.

Применение: tcpvcon [-a] [-c] [-n] [имя процесса или PID]

Исходный текст программы Netstatp

Хотите знать, как работает программа TCPView? На примере исходного текста программы Netstatp показано, как можно запрограммировать некоторые функции программы TCPView. На примере этой программы показано, как использовать интерфейсы IP Helper (см. описание в документах на узле MSDN), чтобы получить список конечных точек соединений по протоколу TCP/IP. Однако обратите внимание, что программа netstatp не выводит имена процессов в системах NT 4 и Windows 2000, как это делают программы TCPView и TCPVCon.

Статья базы знаний Microsoft о программе TCPView

Данная статья базы знаний Майкрософт посвящена программе TCPView:

Взаимосвязанная служебная программа

TDImon - показывает активность с использованием протоколов TCP и UDP в реальном времени.

Если вам понравилась программа TCPView, то программа TCPView Pro понравится вам еще больше. Программа TCPView Pro, разработанная компанией Winternals Software, обладает рядом функций, благодаря которым она является намного более мощным и полезным средством, чем программа TCPView. Это такие функции: просмотр данных о процессах, которым принадлежат конечные точки открытых соединений (также действует в системе Windows 9x)

• просмотр активности процессов с использованием протоколов TCP и UDP в реальном времени
• использование усовершенствованных методов фильтрации для показа только необходимых данных.
• и многое другое...

Программа TCPView Pro поставляется в составе пакета Winternals Administrator"s Pak.

В современных системах цифрового телевидения для обеспечения помехоустойчивой передачи цифровых телевизионных сигналов по радиоканалу используются наиболее совершенные коды Рида-Соломона (Reed-Solomon),требующие добавления двух проверочных символов в расчете на одну исправляемую ошибку . Коды Рида-Соломона обладают высокими корректирующими свойствами, для них разработаны относительно простые и конструктивные методы кодирования. Коды Рида-Соломона не являются двоичными. Это надо понимать в том смысле, что символами кодовых слов являются не двоичные знаки, а элементы множества чисел, состоящего более чем из двух знаков (хотя, конечно, при передаче каждый символ заменяется соответствующей двоичной комбинацией).

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

Чтобы получить более детальное представление о кодах Рида-Соломона посмотрим, какое место они занимают в классификации корректирующих кодов (рис. 4.4).

Корректирующие коды разделяются на блочные и сверточные (непрерыв­ные). Блочные коды основаны на перекодировании исходной кодовой комбина­ции (блока), содержащейk информационных символов, в передаваемую кодо­вую комбинацию, содержащуюn >k символов. Дополнительныер = n – k сим­волов зависят только отk символов исходной кодовой комбинации. Следова­тельно, кодирование и декодирование осуществляются всегда в пределах од­ной кодовой комбинации (блока). В противоположность этому всверточных кодах кодирование и декодирование осуществляются непрерывно над после­довательностью двоичных символов.

Блочные коды бывают разделимые и неразделимые. В разделимых кодах можно в каждой кодовой комбинации указать, какие символы являются инфор­мационными, а какие проверочными. Внеразделимых кодах такая возмож­ность отсутствует.

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

Рис. 4.4. Место кодов Рида-Соломона в классификации корректирующих кодов

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

Перейдем к более подробному знакомству с циклическими кодами .

В первую очередь введем запись кодовой комбинации или, как часто назы­вают ее в литературе, кодового вектора в виде полинома. Пусть имеется кодо­вая комбинация a 0 a 1 a 2 ...a n –1 , гдеа 0 – младший разряд кода,a n –1 – старший раз­ряд кода. Соответствующий ей полином имеет вид

,

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

Над полиномами, представляющими кодовые комбинации, определена ма­тематическая операция умножения. Особенность этой операции по сравнению с общепринятой заключается в том, что коэффициенты при х всех степеней суммируются по модулю 2, а показатели степених при перемножении сумми­руются по модулюn , поэтомух n = 1.

Далее введем понятие производящего полинома . Производящим полино­мом порядка (n – k ) может быть полином со старшей степенью х , равной (n – k ), на который без остатка делится двучлен (1 + х n ). Разрешенные кодовые комби­нации получаются перемножением полиномов порядка k – 1, выражающих исходные кодовые комбинации, на производящий полином.

Циклические коды имеют следующее основное свойство. Если кодовая ком­бинация a 0 a 1 a 2 ...a n –1 является разрешенной, то получаемая из нее путем цик­лического сдвига кодовая комбинацияa n –1 a 0 a 1 ...a n –2 также является разрешен­ной в данном коде. При записи в виде полиномов операция циклического сдви­га кодового слова сводится к умножению соответствующего полинома нах с учетом приведенных ранее правил выполнения операции умножения.

Циклический код с производящим полиномом
строится следующим об­разом.

1. Берутся полиномы
,
,
, ...,
.

2. Кодовые комбинации, соответствующие этим полиномам, записывают в виде строк матрицы G , называемойпроизводящей матрицей .

3. Формируется набор разрешенных кодовых комбинаций кода. В него вхо­дит нулевая кодовая комбинация, k кодовых комбинаций, указанных в п. 1, а также суммы их всевозможных сочетаний. Суммирование осуществляется по­разрядно, причем каждый разряд суммируется по модулю 2 . Общее число полученных таким образом разрешенных кодовых комбинаций равно 2 k , что соответствует числу информационных разрядов кода.

Для построения декодера в первую очередь получают производящий поли­ном
порядкаk для построенияисправляющей матрицы Н :

.

Строками исправляющей матрицы Н будут кодовые комбинации, определяемые полиномами
,
, ...,
, где
– это записанный в об­ратном порядке полином
. Исправляющая матрица имеетn столбцов иn – k строк.

При декодировании принятая кодовая комбинация a 0 a 1 a 2 ...a n –1 скалярно умножается на каждую строку исправляющей матрицы. Эта операция может быть записана в виде соотношения:

где h ji – элементыj -той строки матрицыН . Полученныеn – k чиселc j образуютисправляющий вектор илисиндром . Если ошибок нет, то всеc j = 0. Если же при передаче данной кодовой комбинации возникла ошибка, то некоторые из чиселc j не равны 0. По тому, какие именно элементы исправляющего вектора отличны от нуля, можно сделать вывод о том, в каких разрядах принятой кодо­вой комбинации есть ошибка и, следовательно, исправить эти ошибки.

Рассмотрим пример, часто встречающийся в литературе. Построим цикли­ческий код с n = 7;k = 4. Для этого представим двучлен 1 +х 7 в виде произве­дения :

В обычной алгебре это равенство, конечно, не выполняется, но если ис­пользовать для приведения подобных вместо обычного сложения операцию суммирования по модулю 2, а при сложении показателей степеней – операцию суммирования по модулю 7, то равенство окажется справедливым.

В качестве производящего многочлена возьмем 1 + х +х 3 . Умножаем его нах ,х 2 их 3 и получаем многочленых +х 2 +х 4 ;х 2 +х 3 +х 5 ;х 3 +х 4 +х 6 . Затем запи­сываем производящую матрицуG , причем в каждой строке матрицы младший разряд кодовой комбинации расположен первым слева.

.

Далее формируем набор из 15 допустимых кодовых комбинаций: 00000000, 1101000, 0110100, 0011010, 0001101, 1011100, 0101110, 0010111, 1000110, 0100011, 1111111, 1010001, 1000110, 0100011, 1001011. В этих записях млад­шие биты слева, а старшие – справа.

Перемножив первые два сомножителя в, получаем производящий мно­гочлен для исправляющей матрицы: 1 + х +х +х 4 . Затем умножаем его нах их 2 и получаем еще две строки этой матрицы, которая в результате имеет такой вид (в отличие от матрицыG здесь младшие разряды соответствующих поли­номов расположены справа):

.

Пусть принята кодовая комбинация 0001101, входящая в набор допустимых. Найдем скалярные произведения этой кодовой комбинации со всеми строками матрицы Н :

Пусть теперь принята кодовая комбинация 0001100, в которой последний (старший) бит содержит ошибку. Скалярные произведения принятой кодовой комбинации на строки исправляющей матрицы имеют вид:

Таким образом, получен синдром (1, 0, 0). Если ошибка оказывается в другом бите кодовой комбинации, то получается другой синдром.

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

Различные виды циклических кодов получаются с помощью различных про­изводящих полиномов. Существует развитая математическая теория этого во­проса . Среди большого количества циклических кодов к числу наиболее эффективных и широко используемых относятся коды Бозе-Чоудхури-Хоквингема (ВСН-коды – по первым буквам фамилий Bose,Chaudhuri,Hockwinhamили в русскоязычной записи БЧХ-коды), являющиесяобобщением кодов Хемминга на случай направления нескольких ошибок. Они образуют наилучший среди известных класснеслучайных кодов для каналов, в которых ошибки в последовательных символах возникают независимо. Например, БЧХ-код (63, 44), используемый в системе спутникового цифрового радиовещания, по­зволяет исправить 2 или 3 ошибки, обнаружить 4 или 5 ошибок на каждый блок из 63 символов. Относительная скорость такого кода равнаR = 44/63 = 0,698.

Одним из видов ВСН-кодов являются коды Рида-Соломона. Эти коды отно­сятся к недвоичным кодам , так как символами в них могут быть многоразряд­ные двоичные числа, например, целые байты. В Европейском стандарте циф­рового телевидения DVB используется код Рида-Соломона, записываемый как (204, 188, 8), где 188 – количество информационных байт в пакете транс­портного потока MPEG-2, 204 – количество байт в пакете после добавления проверочных символов, 8 – минимальное кодовое расстояние между допусти­мыми кодовыми комбинациями. Таким образом, в качестве кодовых комбина­ций берутся целые пакеты транспортного потока, содержащие 1888 = 1504 информационных бита, а добавляемые проверочные символы содержат 168 = 128 бит. Относительная скорость такого кода равна 0,92. Этот код Рида-Соломона позволяет эффективно исправлять до 8 принятых с ошибками байт в каждом транспортном пакете.

Отметим также, что используемый в цифровом телевизионном вещании код Рида-Соломона часто называют укороченным . Смысл этого термина состоит в следующем. Из теории кодов Рида-Соломона следует, что если символом кода является байт, то полная длина кодового слова должна составлять 255 байт (239 информационных и 16 проверочных). Однако, пакет транспортного потокаMPEG-2 содержит 188 байт. Чтобы согласовать размер пакета с параметра­ми кода, перед кодированием в начало каждого транспортного пакета добав­ляют 51 нулевой информационный байт, а после кодирования эти дополни­тельные нулевые байты отбрасывают.

В приемнике для каждого принятого транспортного пакета, содержащего 204 байта, вычисляются синдромы и находятся два полинома: «локатор», корни ко­торого показывают положение ошибок, и «корректор» (evaluator), дающий зна­чение ошибок. Ошибки корректируются, если это возможно. Если же коррекция невозможна (например, ошибочных байт более 8) данные в пакете не изме­няются, а сам пакет помечается путем установки флага (первый бит после синхробайта), как содержащий неустранимые ошибки. В обоих случаях 16 избы­точных байт удаляются, и после декодирования длина транспортного пакета становится равной 188 байт.