СПОСОБ СОВМЕСТНОГО АРИФМЕТИЧЕСКОГО И ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ
METHOD OF COMBINED ARITHMETIC AND NOISE-IMMUNE ENCODING AND DECODING

Заявленное техническое решение относится к области электросвязи и информационных технологий, а именно к технике сжатия и восстановления избыточной двоичной информации и ее помехоустойчивого кодирования и декодирования при передаче информации по каналам с ошибками.
Заявленное изобретение может быть использовано для обеспечения достоверности избыточной двоичной информации, передаваемой по каналам с ошибками.
Известен способ адаптивного помехоустойчивого кодирования и декодирования по патенту РФ 2375824 МПК Н04 L1/20 (2006.01) от 10.12.2009, заключающийся в том, что на передающей стороне исходную информацию кодируют помехоустойчивым кодом с переменными параметрами, далее помехоустойчивый код передают в канал связи, на приемной стороне помехоустойчивый код декодируют с обнаружением и исправлением ошибок в зависимости от корректирующей способности выбранного кода, по результатам декодирования помехоустойчивого кода оценивают качество канала связи и выбирают переменные параметры помехоустойчивого кода, обеспечивающие заданную вероятность правильного приема помехоустойчивого кода, и далее эти параметры помехоустойчивого кода сообщают на передающую сторону, отличающийся тем, что на приемной стороне по результатам декодирования помехоустойчивого кода рассчитывают начальную величину избыточности помехоустойчивого кода, обеспечивающую заданную вероятность правильного приема помехоустойчивого кода, оценивают вероятность правильного приема помехоустойчивого кода с выбранными параметрами, вычисляют величину отклонения полученной вероятности правильного приема помехоустойчивого кода от заданной вероятности правильного приема кода и в зависимости от величины этого отклонения корректируют величину избыточности помехоустойчивого кода, которую передают на передающую сторону, где формируют помехоустойчивый код с полученной избыточностью.
Недостатком указанного аналога является неэффективное использование пропускной способности канала передачи, вызванное отсутствием сжатия избыточной двоичной информации при обмене данными по каналам передачи с ошибками.
Известен также способ совместного сжатия и помехоустойчивого кодирования и декодирования речевых сообщений, описанный, например, в книге С.Н. Кириллов, В.Т. Дмитриев, Д.Е. Крысяев, С.С. Попов "Исследование качества передаваемой речевой информации при различном сочетании алгоритмов кодирования источника и канала связи в условиях воздействия помех". -Рязань, Вестник РГРТУ, Выпуск 23, 2008. Данный способ заключается в том, что предварительно формируют множество способов сжатия речевого сигнала, таких как импульсно-кодовая модуляция, адаптивная дельта-модуляция, адаптивная дифференциальная импульсно-кодовая модуляция, и множество способов помехоустойчивого кодирования, таких как кодирование Хэмминга, кодирование Боуз-Чоудхури-Хоквингема, на передающей стороне от отправителя получают очередную часть речевого сигнала длиною речевая фраза, который преобразуют в сжатую двоичную последовательность с помощью одного из способов сжатия речевого сигнала, выполняют помехоустойчивое кодирование сжатой двоичной последовательности с помощью одного из способов помехоустойчивого кодирования, передают на приемную сторону по каналу прямой связи очередную часть кодированной последовательности вместе с информацией об использованном способе сжатия речевого сигнала и способе помехоустойчивого кодирования, на приемной стороне получают очередную часть принятой последовательности, очередную часть принятой последовательности последовательно декодируют с использованием соответствующих способа помехоустойчивого декодирования и способа восстановления речевого сигнала, вычисляют оценку качества восстановленного речевого сигнала и полученную оценку сравнивают с пороговым значением качества, если вычисленная оценка качества восстановленного речевого сигнала не хуже предварительно установленного порогового значения качества, то передают получателю очередную часть восстановленной информационной последовательности и передающей стороне от отправителя получают очередную часть речевого сигнала и выполняют последующие действия, иначе передают по каналу обратной связи требование изменить способ сжатия речевого сигнала и способ помехоустойчивого кодирования, и выполняют последующие действия.
Недостатком указанного аналога является большая задержка передачи сообщений по каналу связи, вызванная необходимостью подбора подходящих способа сжатия речевого сигнала и способа помехоустойчивого кодирования.
Наиболее близким по своей технической сущности к заявленному способу совместного арифметического и помехоустойчивого кодирования и декодирования является способ совместного арифметического и помехоустойчивого кодирования и декодирования по патенту США 6892343 МПК Н04 М13/00 (2006.01) от 10.05.2005. Способ - прототип совместного арифметического и помехоустойчивого кодирования и декодирования заключается в том, что предварительно на передающей стороне устанавливают начальный интервал арифметического кодирования и на приемной стороне соответствующий ему начальный интервал арифметического декодирования, на передающей стороне от источника информации принимают очередную часть информационной последовательности длиной k≥1 бит, разделяют текущий интервал арифметического кодирования длиною D>2 на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, из предварительно сформированного множества выбирают проверочные символы длиной r≥1 бит и формируют очередную часть помехоустойчивой последовательности из очередной части информационной последовательности и выбранных проверочных символов, выполняют арифметическое кодирование очередной части помехоустойчивой последовательности в очередную часть кодированной последовательности, преобразуют очередную часть кодированной последовательности в очередную часть модулированной последовательности, передают очередную часть модулированной последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные части информационной последовательности, на приемной стороне принимают очередную часть последовательности, преобразуют ее в двоичную последовательность, которую запоминают, разделяют текущий интервал арифметического декодирования длиною DD>2 на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, запомненные очередные части принятой последовательности арифметически декодируют в очередные части декодированной последовательности, из которых выделяют очередные части восстановленной информационной последовательности и декодированные проверочные символы, если декодированные проверочные символы принадлежат предварительно сформированному множеству проверочных символов, то делают вывод об отсутствии ошибок передачи и передают получателю очередную часть восстановленной информационной последовательности, иначе поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности и выполняют их арифметическое декодирование до достижения вывода об отсутствии ошибок передачи, выполняют перечисленные действия на приемной стороне до тех пор, пока на приемной стороне поступают очередные части принятой последовательности.
Особенностью способа-прототипа является то, что на передающей стороне выполняют выбор проверочных символов, а затем сжатие очередных частей информационной последовательности и проверочных символов путем арифметического кодирования, а на приемной стороне после арифметического декодирования обнаруживают ошибки передачи при их наличии, а при их обнаружении методом проб и ошибок выполняют их исправление. Способ-прототип совместного арифметического и помехоустойчивого кодирования и декодирования обеспечивает возможность обнаружения и исправления ошибок передачи.
w
Однако в данном способе-прототипе совместного арифметического и помехоустойчивого кодирования и декодирования информационной последовательности исправление ошибок передачи выполняют методом перебора, поочередно инвертируя один или несколько битов в запомненных очередных частях принятой последовательности и выполняя их арифметическое декодирование до достижения вывода об исправлении этих ошибок. При длине N бит запомненных очередных частей принятой последовательности и числе W исправляемых ошибок это требует параллельной работы порядка N/2 арифметических декодеров с соответствующим числом устройств обнаружения ошибок. При арифметическом декодировании сжатых избыточных двоичных последовательностей наличие ошибок передачи выявляется при длине запомненных очередных частях принятой последовательности вплоть до десятков бит и более. Поэтому в данном способе-прототипе совместного арифметического и помехоустойчивого кодирования и декодирования исправление ошибок передачи при кратности ошибок более одной требует использования многих тысяч арифметических декодеров с соответствующим числом устройств обнаружения ошибок, что является практически нереализуемым.
Таким образом, недостатком ближайшего аналога (прототипа) совместного арифметического и помехоустойчивого кодирования и декодирования информационной последовательности является низкая помехоустойчивость передачи очередных частей кодированной последовательности, обусловленная практической невозможностью исправления ошибок передачи при кратности ошибок более одной.
Техническим результатом заявляемого решения является разработка способа совместного арифметического и помехоустойчивого кодирования и декодирования, обеспечивающего повышение помехоустойчивости передачи очередных частей кодированной последовательности при воздействии многократных ошибок передачи.
Указанный технический результат в заявляемом способе совместного арифметического и помехоустойчивого кодирования и декодирования достигается тем, что в известном способе совместного арифметического и помехоустойчивого кодирования и декодирования, заключающимся в том, что предварительно на передающей стороне устанавливают начальный интервал арифметического кодирования и на приемной стороне соответствующий ему начальный интервал арифметического декодирования, на передающей стороне от источника информационной последовательности принимают очередную часть информационной последовательности длиной k≥1 бит, разделяют текущий интервал арифметического кодирования длиною D>2 на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, выполняют арифметическое кодирование очередной части последовательности в очередную часть кодированной последовательности, передают очередную часть последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные части информационной последовательности, на приемной стороне принимают последовательность, разделяют текущий интервал арифметического декодирования длиною DD>2 на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, арифметически декодируют принятую последовательность в очередные части декодированной последовательности, из которых выделяют очередные части восстановленной информационной последовательности, передают получателю очередную часть восстановленной информационной последовательности, выполняют перечисленные действия на приемной стороне до тех пор, пока на приемной стороне поступает последовательность, дополнительно предварительно устанавливают предельное число Z≥2 альтернативных принятых последовательностей и величину задержки декодирования T≥2 очередных частей восстановленной информационной последовательности, а также значение метрики альтернативных принятых последовательностей в нулевое значение.
β
β
β
На передающей стороне после арифметического кодирования очередной части информационной последовательности в очередную часть кодированной последовательности разделяют текущий интервал арифметического кодирования длиною D на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, из которых выделяют текущий разрешенный подинтервал кодирования длиною D≥1, длину которого выбирают как D=β⋅D, где коэффициент помехоустойчивости β выбирают в пределах 0<β<1. Устанавливают текущий интервал арифметического кодирования равным текущему разрешенному подинтервалу кодирования длиною D.
Передают очередную часть кодированной последовательности на приемную сторону, а на приемной стороне принимают очередной бит последовательности. Разделяют текущий интервал арифметического декодирования длиною DD каждой альтернативной принятой последовательности на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, для каждой альтернативной принятой последовательности формируют продолжение последовательности в виде нулевого символа и продолжение последовательности в виде единичного символа. Устанавливают значение метрики продолжения последовательности в виде нулевого символа относительно очередного бита принятой последовательности как нулевое значение, если очередной бит принятой последовательности является нулевым битом, иначе устанавливают как единичное значение. Устанавливают значение метрики продолжения последовательности в виде единичного символа относительно очередного бита принятой последовательности как нулевое значение, если очередной бит принятой последовательности является единичным битом, иначе устанавливают как единичное значение.
β
β
Для каждой альтернативной принятой последовательности с ее продолжением последовательности вычисляют значение ее метрики, для чего суммируют значения метрики данной последовательности и метрики ее продолжения последовательности. Арифметически декодируют каждую альтернативную принятую последовательность с ее продолжением последовательности в очередные части соответствующей ей альтернативной декодированной последовательности, из которых выделяют очередные части альтернативной восстановленной информационной последовательности. После выделения k-го бита очередной части альтернативной восстановленной информационной последовательности разделяют текущий интервал арифметического декодирования длиною DD каждой альтернативной принятой последовательности на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, из которых выделяют текущий разрешенный подинтервал декодирования длиною DD≥1, длину которого выбирают как DD=β⋅DD.
β
Устанавливают текущий интервал арифметического декодирования каждой альтернативной принятой последовательности равным ее текущему разрешенному подинтервалу декодирования длиною DD, если текущее значение принятой последовательности находится в пределах текущего интервала декодирования альтернативной принятой последовательности, то запоминают очередные части альтернативной восстановленной информационной последовательности, соответствующей этой последовательности, иначе стирают данную альтернативную принятую последовательность с ее продолжением последовательности. Сравнивают между собой значения метрики альтернативных принятых последовательностей с их продолжениями последовательности и выбирают из них не более предельного числа Z альтернативных принятых последовательностей, имеющих наименьшие значения метрики, которые дополняют соответствующими им продолжениями последовательности, для этих альтернативных принятых последовательностей запоминают очередные части соответствующих им альтернативных восстановленных информационных последовательностей и значения метрики. Если номер очередной части принятой последовательности меньше величины задержки декодирования Т очередных частей восстановленной информационной последовательности, то выполняют перечисленные действия на приемной стороне, иначе сравнивают между собой значения метрики альтернативных принятых последовательностей и выбирают из них последовательность с наименьшим значением метрики и передают получателю в качестве очередной части восстановленной информационной последовательности соответствующую выбранной альтернативной принятой последовательности часть альтернативной восстановленной информационной последовательности, номер которой на (T-1) меньше номера очередной части этой альтернативной восстановленной информационной последовательности.
Выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные биты принятой последовательности.
В предлагаемой совокупности действий на передающей стороне при арифметическом кодировании очередной части информационной последовательности в очередную часть кодированной последовательности последняя формируется в соответствии с текущим разрешенным подинтервалом кодирования, а на приемной стороне при декодировании очередных частей принятой последовательности стирают те альтернативные принятые последовательности, которые не могут быть сформированы на передающей стороне, среди оставшихся сохраняют и продолжают ограниченное число Z альтернативных принятых последовательностей с их продолжениями последовательности, имеющих наименьшие значения метрики, и с задержкой декодирования T среди лучших по критерию метрики продолжаемых альтернативных принятых последовательностей выбирают из них последовательность с наименьшим значением метрики, которая с наибольшей вероятностью совпадает со сформированной на передающей стороне кодированной последовательностью. Тем самым выполняется исправление ошибок канала передачи, причем кратность исправленных ошибок в принятой последовательности равна значению метрики выбранной альтернативной принятой последовательности. Благодаря стиранию при декодировании очередных битов принятой последовательности альтернативных принятых последовательности, которые не обеспечивают исправление ошибок, и продолжения ограниченного числа Z альтернативных принятых последовательностей с их продолжениями последовательности, которые обеспечивают максимизацию вероятности исправления ошибок передачи, обеспечивается возможность исправления многократных ошибок передачи. Кратность исправляемых ошибок канала передачи увеличивается при увеличении коэффициента помехоустойчивости β, предельного числа Z альтернативных принятых последовательностей и величины задержки декодирования T очередных частей восстановленной информационной последовательности.
Поэтому указанная новая совокупность действий при выполнении совместного арифметического и помехоустойчивого кодирования и декодирования информационной последовательности позволяет обеспечить повышение помехоустойчивости передачи очередных частей кодированной последовательности при воздействии многократных ошибок передачи.
Заявленный способ поясняется чертежами, на которых показаны:
- на фиг. 1 - общая схема совместного арифметического и помехоустойчивого кодирования и декодирования;
- на фиг. 2 - схема блока декодирования 7;
- на фиг. 3 - алгоритм совместного арифметического и помехоустойчивого кодирования на передающей стороне;
- на фиг. 4 - таблица состояний совместного арифметического и помехоустойчивого кодирования первых шести очередных частей информационной последовательности;
- на фиг. 5 - временные диаграммы совместного арифметического и помехоустойчивого кодирования первых двух очередных частей информационной последовательности;
- на фиг. 6 - временные диаграммы совместного арифметического и помехоустойчивого кодирования первых шести очередных частей информационной последовательности;
- на фиг. 7 - временные диаграммы совместного арифметического и помехоустойчивого декодирования первых семнадцати битов принятой последовательности на приемной стороне;
- на фиг. 8 - алгоритм совместного арифметического и помехоустойчивого декодирования на приемной стороне;
- на фиг. 9 - представление альтернативных принятых последовательностей в виде древовидной структуры;
- на фиг. 10 - примерный вид выбираемых не более Z=13 альтернативных принятых последовательностей;
- на фиг. 11 - таблица состояний декодирования альтернативной принятой последовательности вида "0100 0000 0";
- на фиг. 12 - таблица состояний декодирования альтернативной принятой последовательности вида "0100 0000 1";
- на фиг. 13 - таблица состояний декодирования альтернативной принятой последовательности вида "0100 0000 0001 111";
- на фиг. 14 - таблица состояний декодирования альтернативной принятой последовательности вида "0100 0000 1101 1110 1";
- на фиг. 15 - полученные значения вероятности исправления двух и трех кратных ошибок при значении коэффициента помехоустойчивости β=0,4.
Реализация заявленного способа представлена на примере системы совместного арифметического и помехоустойчивого кодирования и декодирования, показанной на фиг. 1. На передающей стороне выполняют совместное арифметическое и помехоустойчивое кодирование очередных частей информационной последовательности (ИП), а на приемной стороне - совместное арифметическое и помехоустойчивое декодирование принятой последовательности с исправлением ошибок канала передачи. На передающей стороне формирователь текущего нулевого подинтервала 1 и формирователь текущего единичного подинтервала 2 разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа. При получении от отправителя нулевого символа очередной части информационной последовательности увеличивается текущий подинтервал кодирования нулевого символа и уменьшается текущий подинтервал кодирования единичного символа, а при получении от отправителя единичного символа очередной части информационной последовательности увеличивается текущий подинтервал кодирования единичного символа и уменьшается текущий подинтервал кодирования нулевого символа. На основе данных текущих подинтервалов очередные двоичные символы очередной части информационной последовательности кодируют в арифметическом кодере 3, после кодирования всех двоичных символов очередной части информационной последовательности формирователь текущего нулевого подинтервала 1 и формирователь текущего единичного подинтервала 2 разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, из которых в формирователе текущего разрешенного подинтервала 4 выделяют текущий разрешенный подинтервал кодирования и устанавливают текущий интервал арифметического кодирования равным текущему разрешенному подинтервалу кодирования. С выхода арифметического кодера 3 очередную часть кодированной последовательности передают по каналу передачи 5 на приемную сторону.
На приемной стороне в Z блоках декодирования 6 принимают очередные биты принятой последовательности. Схема блока декодирования 6 показана на фиг. 2. В каждом блоке декодирования 6 формирователь альтернативной принятой последовательности (АПП) с нулевым продолжением 6.1 и формирователь АПП с единичным продолжением 6.8 формируют альтернативные принятые последовательности с соответствующими продолжениями последовательности, которые в арифметическом декодере 6.2 и арифметическом декодере 6.9, соответственно, арифметически декодируют в очередные части соответствующих им альтернативных декодированных последовательностей. При арифметическом декодировании в арифметическом декодере 6.2 нулевого символа очередной части восстановленной информационной последовательности из АПП с нулевым продолжением в формирователе текущего нулевого подинтервала декодирования 6.3 и формирователе текущего единичного подинтервала декодирования 6.4 увеличивается текущий подинтервал декодирования нулевого символа и уменьшается текущий подинтервал декодирования единичного символа для данной АПП, а при декодировании единичного символа - увеличивается текущий подинтервал декодирования единичного символа и уменьшается текущий подинтервал декодирования нулевого символа для данной АПП. После декодирования очередной части восстановленной информационной последовательности формирователь текущего нулевого подинтервала 6.3 и формирователь текущего единичного подинтервала 6.4 разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, из которых в формирователе текущего разрешенного подинтервала декодирования 6.5 выделяют текущий разрешенный подинтервал декодирования и устанавливают текущий интервал арифметического декодирования равным текущему разрешенному подинтервалу декодирования.
Аналогичные действия выполняют при декодировании двоичных символов из АПП с единичным продолжением с использованием формирователя АПП с единичным продолжением 6.8, арифметического декодера 6.9, формирователя текущего нулевого подинтервала 6.10, формирователя текущего единичного подинтервала 6.11 и формирователя текущего разрешенного подинтервала декодирования 6.12.
В блоке вычисления метрики АПП 6.7 для каждой альтернативной принятой последовательности с ее продолжением вычисляют значение ее метрики суммированием метрики самой последовательности и метрики ее продолжения, где значения метрики продолжения последовательности устанавливают в соответствующее значение в зависимости от соотношения между двоичным значением продолжения последовательности и значением очередного бита принятой последовательности. Из блока вычисления метрики АПП 6.7 вычисленные значение метрики каждой альтернативной принятой последовательности с ее продолжением передают в блок выбора АПП 7.
Если при проверке в блоке проверки подинтервала 6.6, соответственно, в блоке проверки подинтервала 6.13, текущее значение принятой последовательности находится в пределах текущего интервала арифметического декодирования соотве5тствующей альтернативной принятой последовательности с ее продолжением последовательности, то в блоке выбора АПП 7 запоминают очередные части альтернативной восстановленной информационной последовательности, соответствующие альтернативной принятой последовательности с ее продолжением, иначе стирают данную альтернативную принятую последовательность с ее продолжением.
В блоке выбора АПП 7 сравнивают между собой значения метрики альтернативных принятых последовательностей с их продолжениями и выбирают из них не более предельного числа Z альтернативных принятых последовательностей, имеющих наименьшие значения метрики, которые дополняют соответствующими им продолжениями последовательности, для этих альтернативных принятых последовательностей запоминают очередные части соответствующей им альтернативной восстановленной информационной последовательности и значения метрики.
Начиная с T-го номера очередной части восстановленной информационной последовательности в блоке выбора АПП 7 сравнивают между собой значения метрики альтернативных принятых последовательностей и выбирают из них альтернативную принятую последовательность с наименьшим значением метрики и передают получателю в качестве очередной части восстановленной информационной последовательности соответствующую выбранной альтернативной принятой последовательности часть альтернативной восстановленной информационной последовательности, номер которой на (T-1) меньше номера очередной части этой последовательности.
В способе реализуется следующая последовательность действий.
Алгоритм совместного арифметического и помехоустойчивого кодирования на передающей стороне представлен на фигуре 3.
R
Способы предварительной установки на передающей стороне начального интервала арифметического кодирования длиною D>2 и на приемной стороне соответствующего ему начального интервала арифметического декодирования длиною DD>2 известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Начальный интервал арифметического кодирования начинается от его начального нижнего значения и заканчивается его начальным верхним значением. Начальное нижнее значение интервала кодирования устанавливают в минимальное значение интервала кодирования, а начальное верхнее значения интервала кодирования - в максимальное значение этого интервала. Например, при представлении значений интервала кодирования восемью двоичными символами (разрядность представления интервалов N=8 бит), начальное нижнее значение интервала кодирования арифметического кодирования L[0] в момент времени t=0 устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 0000 0000 в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования H[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или 1111 1111 в двоичном представлении. Пример начального интервала арифметического кодирования длиною D=255 представлен на фиг. 4 при t=0 (первая строка) и на фиг. 5 при t=0.
Также предварительно устанавливают предельное число Z≥2 альтернативных принятых последовательностей и величину задержки декодирования T≥2 очередных частей восстановленной информационной последовательности, а также устанавливают значение метрики альтернативных принятых последовательностей в нулевое значение. Способы предварительной установки предельного числа Z альтернативных принятых последовательностей и величины задержки декодирования T очередных частей восстановленной информационной последовательности, известны и описаны, например, в книге Д. Прокис "Цифровая связь". - М., Радио и связь, 2000, стр. 328-349. Например, для исправления двукратных ошибок рекомендуется выбирать предельное число Z альтернативных принятых последовательностей из диапазона значений 8…16, для исправления трехкратных ошибок рекомендуется выбирать предельное число Z альтернативных принятых последовательностей из диапазона значений 17…32, с учетом того, что при увеличении выбранного числа Z можно исправить большее число ошибок передачи, но при этом линейно растет сложность устройств реализации исправления ошибок. Например, для рассматриваемого далее примера установим предельное число Z альтернативных принятых последовательностей равным Z=13.
Величина задержки декодирования T очередных частей восстановленной информационной последовательности (ВИП) численно равна количеству очередных частей восстановленной информационной последовательности, при котором остается единственная альтернативная принятая последовательность, имеющая наименьшее значение метрики среди значений метрики альтернативных принятых последовательностей. Следовательно, начиная с этого момента можно принимать решение о значении самой ранней по времени декодирования части ВИП. Например, для класса методов декодирования дискретных последовательностей списком размера Z, а заявленный способ в части декодирования является развитием этого класса методов, описанных в книге Д. Прокис "Цифровая связь". - М., Радио и связь, 2000, стр. 328-349, рекомендуется практически выбирать величину задержки декодирования численно равную (1…3)×Z, что позволяет исправлять различные комбинации ошибок передачи без существенного роста сложности реализации исправления ошибок. Например, для рассматриваемого далее примера для сокращения объема описаний операций декодирования с учетом установим величину задержки декодирования T очередных частей ВИП численно равную T=4.
Способы предварительной установки значения метрики альтернативных принятых последовательностей в нулевое значение известны и описаны, например, в книге Б. Скляр "Цифровая связь. Теоретические основы и практическое применение". - М., Издательский дом "Вильяме", 2003, стр. 432-434. Изначально, до начала приема последовательности на приемной стороне альтернативные принятые последовательности имеют нулевую длину.
На передающей стороне от источника информационной последовательности принимают очередную часть информационной последовательности длиной k≥1 бит. Примерный вид первых шести очередных частей двоичной ИП длиной k=2 бита показан на фиг. 6(a). Например, первая часть ИП имеет вид "00", вторая часть - "01" и т.д. Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.
0
1
0
1
0
1
0
Способы разделения текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Для арифметического кодирования очередного по счету, t-го символа, где t=1, 2, …, длину текущего интервала арифметического кодирования D[t-1], равную D[t-1]=H[t-1]-L[t-1], разделяют на длину текущего подинтервала нулевого символа D[t-1] и длину текущего подинтервала единичного символа D[t-1]. Для этого подсчитывают текущее число нулевых символов ИП N[t-1] и текущее число единичных символов ИП N[t-1]. Например, в начальный момент при t=0 текущее число нулевых символов ИП N[0] установлено в значение 1 и текущее число единичных символов ИП N[0] установлено в значение 1. Способы установки в начальный момент арифметического кодирования числа нулевых и единичных символов ИП в единичное значение известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 124-130. Например, как показано на фиг. 4 в первой строке при t=0 указано единичное число нулевых символов ИП (графа N0) и единичное число единичных символов ИП (графа N1). В графе N указывается общее число принятых с учетом установленных в начальный момент нулевых и единичных символов ИП. При кодировании первого по счету принятого информационного символа, являющегося, например, нулевым символом, текущее число нулевых символов ИП увеличивается на единичное значение: N[1]=2, соответственно, текущее общее число нулевых и единичных символов ИП становится равным N[1]=2, как показано на фиг. 4 во второй строке при t=1.
0
0
0
0
1
Σ1
1
1
0
1
Вычисляют текущую вероятность нулевых символов ИП p[t) по правилу: p[t]=N[t]/(N[t]+N[t]) и текущую вероятность единичных символов ИП p[t] по правилу: p[t]=N[t]/(N[t]+N[t]). Например, как показано на фиг. 4 в первой строке при t=0, указано значение текущей вероятности нулевых символов ИП (графа р0) и значение текущей вероятности единичных нулевых символов ИП (графа p1), где начальные значения равны 0,5.
1
1
1
0
0
1
1
0
Длину текущего подинтервала единичного символа D[t] определяют по формуле вида D[t]=I[t]×p[t], а длину текущего подинтервала нулевого символа D[t] определяют по формуле вида D[t]=I[t]-D[t]. Например, длина начального интервала кодирования D[0] имеет десятичное значение 255, а длина начального подинтервала единичных символов D[0] имеет десятичное значение 128 или 10000000 в двоичном представлении, а длина начального подинтервала нулевых символов D[0] имеет десятичное значение 127 или 01111111 в двоичном представлении. Подинтервал единичных символов расположен сверху подинтервала нулевых символов, как показано, например, на фиг. 5. Верхнюю границу подинтервала нулевого символа обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования включительно до значения Q исключительно, а подинтервал единичного символа простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Начальное значение Q имеет десятичное значение 127, как показано на фиг. 4 в первой строке при t=0.
Способы арифметического кодирования очередной части ИП в очередную часть кодированной последовательности (КП) известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном сжатии двоичных символов очередной части ИП в очередную часть КП в соответствии с текущими значениями интервала кодирования арифметического кодирования и текущими значениями вероятностей нулевых символов и единичных символов ИП. По мере поступления на вход двоичных символов ИП подсчитывают текущее число нулевых и единичных символов ИП, пропорционально которым текущий интервал кодирования арифметического кодирования делят на текущий подинтервал кодирования нулевого символа и текущий подинтервал кодирования единичного символа, в соответствии с которыми арифметический кодер последовательно формирует КП.
При поступлении на вход арифметического кодирования очередного двоичного символа очередной части ИП, являющегося единичным двоичным символом, текущий интервал кодирования этого символа устанавливают равным предыдущему подинтервалу кодирования единичного символа, а при поступлении на вход арифметического кодирования нулевого двоичного символа, текущий интервал кодирования этого символа устанавливают равным предыдущему подинтервалу кодирования нулевого символа. Например, при поступлении на вход арифметического кодирования первого двоичного символа первой части ИП, являющегося нулевым двоичным символом, нижнее значение интервала кодирования первого символа L[1] устанавливают равным начальному нижнему значению интервала кодирования арифметического кодирования L[0], равному, например, десятичному значению 0, а верхнее значение интервала кодирования первого символа арифметического кодирования H[1] устанавливают равным значению Q, равному, например, 127, как показано на фиг. 4 и на фиг. 5 при t=1.
При арифметическом кодировании самый левый бит двоичного представления значения L[l] сравнивают с самым левым битом двоичного представления значения H[1], например, вида 0000 0000 и 0111 1111, соответственно, как показано на фиг. 4 при t=1. При их совпадении значение самого левого бита двоичных представлений значений L[1] и H[1] считывают в качестве очередного бита очередной части кодированной последовательности (Закод. символ на фиг. 4). Например, при кодировании первой части ИП первым битом первой части КП является совпавший при сравнении нулевой двоичный символ, как показано на фиг. 4, третья строка сверху. Считанный бит удаляют из двоичных представлений значений L[1] и H[1], которые уменьшаются до длины 7 бит вида 0000 000 и 1111 111, соответственно. Двоичные символы двоичных представлений значений L[1] и H[1] сдвигают справа налево на один разряд и справа к ним дописывают по нулевому двоичному символу. Например, двоичные представления значений L[1] и H[1] приобретают вид 0000 0000 и 1111 1110, соответственно. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L[1]и H[t] в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования.
После каждого выполнения нормализации повторно самый левый бит двоичного представления нижнего значения интервала кодирования сравнивают с самым левым битом двоичного представления верхнего значения интервала кодирования. При их совпадении значение самого левого бита этих двоичных представлений считывают в качестве следующего бита очередной части КП, иначе переходят к кодированию следующего символа и так далее, как показано на фиг. 4.
0
1
0
1
0
1
После выполнения арифметического кодирования каждого очередного символа уточняют число закодированных нулевых символов ИП и число закодированных единичных символов ИП. Так как первый закодированный символ в указанном примере является нулевым, то число закодированных нулевых символов ИП увеличивают на единичное значение и оно составляет N[1]=2, число закодированных единичных символов информационной последовательности осталось равным N,[1]=1, соответственно, суммарное число закодированных нулевых и единичных информационных символов стало равным 3. Пересчитывают текущее значение вероятности нулевых символов ИП р[1]=2/3 и текущее значение вероятности единичных символов ИП p[1]=1/3. В соответствии с этим длина подинтервала нулевого символа D[1] становится в 2 раза больше длины подинтервала единичного символа D[1], как показано на фиг. 4, третья строка сверху и на фиг. 5 при t=1 после нормализации.
Выполняют арифметическое кодирование следующего двоичного символа ИП, как показано на фиг. 4 и на фиг. 5. При поступлении на вход арифметического кодирования символа, являющегося единичным символом, нижнее значение интервала кодирования устанавливают равным предыдущему значению Q, а верхнее значение интервала кодирования устанавливают равным предыдущему верхнему значению интервала кодирования. Например, при арифметическом кодировании четвертого по счету символа в момент t=5, являющегося единичным символом, в момент t=5, нижнее значение текущего интервала кодирования L[5] устанавливают равным предыдущему значению подинтервала кодирования единичного символа Q[4], равному, например, 123, а верхнее значение текущего интервала кодирования H[5] устанавливают равным верхнему значению предыдущего интервала кодирования H[4], равному, например, 135, как показано на фиг. 4 при t=5.
β
β
β
необн
необн
необн
N
-4
После арифметического кодирования очередной части ИП разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, из которых выделяют текущий разрешенный подинтервал кодирования длиною D≥1, и устанавливают текущий интервал арифметического кодирования равным текущему разрешенному подинтервалу кодирования длиною D, длину которого выбирают как D=β⋅D, где коэффициент помехоустойчивости β выбирают в пределах 0<β<1. Выбор значения коэффициента помехоустойчивости β определяется следующими условиями. При увеличении значения β уменьшается вероятность необнаружения ошибок передачи в принятой последовательности, состоящей из N очередных частей, которая вычисляется по формуле Р=(1-β), как описано в книге Е. Венцель "Теория вероятности". - М., Гос. Издательство физико-математической литературы, 1962, стр. 45-53. Установив желаемое значение вероятности необнаружения Р ошибок передачи в принятой последовательности при N=T, получим требуемое значение β. Например, при выборе значений Р≤10 и N=Т=17 значение коэффициента помехоустойчивости должно быть выбрано не более β=0,4.
0
1
β
β
Например, при выборе значения β=0,4 на фиг. 4 показано разделение текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, из которых выделяют текущий разрешенный подинтервал кодирования. После арифметического кодирования первой части ИП вида "00" длиной k=2 текущий интервал арифметического кодирования от L[2]=0 до H[2]=169 в соответствии с текущей вероятностью нулевых символов ИП p[2]=3/4 и текущей вероятностью единичных символов ИП р[2]=1/4 разделен на текущий подинтервал кодирования нулевого символа от L[2]=0 до Q=127 и на текущий подинтервал кодирования единичного символа от Q=127 до H[2]=169, как показано в пятой строке фиг. 4. Из этих подинтервалов выделяют текущий разрешенный подинтервал кодирования длиною D[2]=0,4⋅D[2]=0,4⋅169=78. Например, пропорционально длине текущего подинтервала кодирования нулевого символа из него в текущий разрешенный подинтервал кодирования выделяют 0,4⋅127=51 единиц длины, и пропорционально длине текущего подинтервала кодирования единичного символа из него в текущий разрешенный подинтервал кодирования выделяют 0,4⋅42=17 единиц длины. В результате текущий разрешенный подинтервал кодирования D[2] простирается от значения Lk[2]=127-51=76 до значения Hk[2]=127+17=154, как показано в пятой строке (выделен, разреш. подинт.) фиг. 4. На фиг. 5 для данного примера проиллюстрировано, что текущий разрешенный подинтервал кодирования выделен из верхней по рисунку части текущего подинтервала кодирования нулевого символа и нижней по рисунку части текущего подинтервала кодирования единичного символа. Текущий разрешенный подинтервал кодирования включает текущее значение Q=127, снизу от этого значения находится 3/4 длины этого подинтервала и сверху - 1/4 длины этого подинтервала.
Далее устанавливают текущий интервал арифметического кодирования равным текущему разрешенному подинтервалу кодирования. Например, как показано в шестой строке фиг. 4 при t=3(код. по разреш. подинт. - кодирование по разрешенному подинтервалу) и на фиг. 5 при t=3, нижняя граница текущего интервала арифметического кодирования стала равной нижней границе текущего разрешенного подинтервала кодирования, а верхняя граница текущего интервала арифметического кодирования стала равной верхней границе текущего разрешенного подинтервала кодирования. При этом текущее значение Q не меняется.
В результате сформирована первая часть кодированной последовательности, которую передают на приемную сторону. При поступлении следующей части ИП ее кодирование в очередную часть КП выполняют идентично. Примерный вид арифметического кодирования первых шести очередных частей ИП вида "00", "01", "00", "01", "00" и "01" в соответствующие очередные части КП вида "0", "10000", "001", "1", "0111" и "101" показан на фиг. 6(б). Заметим, что при фиксированной длине очередных частей ИП в результате их арифметического кодирования сформированы очередные части КП переменной длины, что определяется переменной избыточностью сжимаемых частей ИП.
Способы передачи на приемную сторону очередной части КП известны и описаны, например, в книге А. Г. Зюко, Д. Д. Кловский, М. В. Назаров, Л. М. Финк "Теория передачи сигналов". - М.: Радио и связь, 1986, стр. 11. Примерный вид первых шести частей принятой последовательности (Пр. П) показан на фиг. 7(a). Принятая последовательность общей длиной 17 битов при передаче искажена в девятом и десятом битах принятой последовательности и имеет вид "0100 0000 0001 1110 1".
Алгоритм совместного арифметического и помехоустойчивого декодирования на приемной стороне представлен на фиг. 8.
R
R
R
Для инициализации арифметического декодирования необходимо принять первые по счету N двоичных символов Пр.П, где N есть число двоичных символов представления значений интервалов кодирования и, соответственно, интервалов декодирования. Например, при представлении значений интервала кодирования и интервала декодирования восемью двоичными символами (N=8 бит), принимают первые восемь бит Пр.П вида "0100 0000".
R
R
Опишем в общем виде совместное арифметическое и помехоустойчивое декодирования Пр.П на приемной стороне. Действия совместного арифметического и помехоустойчивого декодирования Пр.П на приемной стороне выполняют путем декодирования нескольких альтернативных принятых последовательностей (АПП). Например, в начальный момент времени имеется единственная альтернативная принятая последовательность, совпадающая с первыми восемью битами Пр.П вида "0100 0000". В момент времени считывания первого после начальных N бит очередной бита принятой последовательности, обозначенного моментом времени t=1, для начальной принятой последовательности, состоящей из первых по счету N двоичных символов принятой последовательности, формируют продолжение АПП в виде нулевого символа и продолжение последовательности в виде единичного символа, как показано на фиг. 9. При считывании следующего бита принятой последовательности (момент времени t=2) для каждого из имеющиеся двух АПП формируют продолжения в виде нулевого символа и продолжение в виде единичного символа, в результате на момент времени t=2 число АПП становится 4, на момент времени t=3 число АПП может достичь 8 и т.д. Представление альтернативных принятых последовательностей в виде описанной древовидной структуры показано на фиг. 9. Такая структура АПП потенциально позволяет исправлять многократные ошибки передачи в принятой последовательности, причем место ошибок в Пр.П может быть произвольным. Для каждой АПП выполняют описанные далее действия совместного арифметического и помехоустойчивого декодирования.
Например, при предварительно установленных предельном числе Z=13 АПП и величине задержки декодирования T=3 очередных частей ВИП примерный вид выбираемых не более Z альтернативных принятых последовательностей показан на фиг. 10. Видно, что в этой структуре, называемой усеченным деревом альтернативных принятых последовательностей, число продолжаемых АПП в каждый момент t не превышает заданного значения Z. Например, для начальной принятой последовательности вида "0100 0000" формируют 2 продолжения: АПП с продолжением последовательности в виде нулевого символа "0100 0000 0", и АПП с продолжением последовательности в виде единичного символа "0100 0000 1". Для АПП с продолжением последовательности в виде нулевого символа "0100 0000 0" значение метрики продолжения последовательности в виде нулевого символа относительно нулевого очередного, девятого по счету на рис. 10 бита, принятой последовательности устанавливают в нулевое значение. Так как метрика самой альтернативной принятой последовательности предварительно установлена в нулевое значение, то АПП с продолжением последовательности в виде нулевого символа "0100 0000 0" имеет значение метрики М=0, как показано на фиг. 10. Для АПП с продолжением последовательности в виде единичного символа "0100 0000 1" значение метрики продолжения последовательности в виде единичного символа относительно нулевого очередного, девятого по счету на рис. 10 бита, принятой последовательности, устанавливают в единичное значение. Соответственно, АПП с продолжением последовательности в виде единичного символа "0100 0000 1" имеет значение метрики М=1, как показано на фиг. 10.
В результате, число продолжаемых АПП при декодировании девятого по счету символа принятой последовательности равно 2, это число не превышает предельного числа Z=13 АПП и обе альтернативные принятые последовательности продолжаются, образуя при декодировании очередного, десятого по счету на рис. 10 бита, принятой последовательности четыре последовательности со значениями метрики от М=0 до М=2, которые при декодировании очередного, одиннадцатого по счету на рис. 10 бита, принятой последовательности образуют 8 последовательностей со значениями метрики от М=0 до М=3, которые при декодировании очередного, двенадцатого по счету на рис. 10 бита, принятой последовательности образуют 16 последовательностей со значениями метрики от М=0 до М=4. Так как число АПП с их продолжениями уже превышает предельное число Z АПП, то из этих последовательностей выбирают Z=13 альтернативных принятых последовательностей с их продолжениями с наименьшими значениями метрики. Одну АПП с ее продолжением с метрикой М=4 и две АПП с их продолжениями с метрикой М=3 стирают, что показано символом "X" на фиг. 10. По принципу максимального правдоподобия в теории помехоустойчивого кодирования, как описано в книге Б. Скляр "Цифровая связь. Теоретические основы и практическое применение". - М., Издательский дом "Вильяме", 2003, стр. 422-431, чем больше альтернативная принятая последовательность с ее продолжением отличается от принятой последовательности по значению метрики М, тем меньше вероятность того что именно она позволит исправить ошибки передачи, что дает основание такую последовательность отбрасывать.
Далее, число продолжаемых АПП при декодировании тринадцатого и четырнадцатого символов по счету символов принятой последовательности остается равным предельному числу Z=13 АПП, а при декодировании пятнадцатого символа по счету символов принятой последовательности число продолжаемых АПП с их продолжениями уменьшается до четырех. Это произошло потому, что во многих ранее продолжаемых АПП текущее значение принятой последовательности оказалось вне пределов текущего интервала арифметического декодирования этих АПП, то есть такие последовательности не могли быть сформированы на передающей стороне и, соответственно, они подлежат стиранию, как показано символом  на фиг. 10. На этом этапе оказалась стертой альтернативная принятая последовательность с ее продолжением вида "0100 0000 0001 111" со значением метрики М=0, которая по этой причине ранее считалась наиболее предпочтительной при выборе среди альтернативных принятых последовательностей.
Далее, число продолжаемых АПП при декодировании шестнадцатого символа по счету символов принятой последовательности увеличилось до восьми, а при декодировании семнадцатого символа снизилось до четырех. В результате декодирования семнадцатого символа принятой последовательности из АПП выделено полные 4 очередные части восстановленной информационной последовательности каждая длиной по 2 бита, как показано на рис. 7(н). Когда номер очередной части (в данном случае четвертой по счету) восстановленной информационной последовательности становится не меньше предварительно установленной величины задержки декодирования T=4 ВИП, то среди альтернативных принятых последовательностей выбирают единственную АПП с наименьшим значением метрики. В нашем случае выбирают АПП вида "0100 0000 1101 1110 1" со значением метрики М=2, для которой выполняется исправление двух ошибок передачи в принятой последовательности. Передают получателю в качестве очередной (в данном случае первой) части ВИП соответствующую выбранной альтернативной принятой последовательности часть альтернативной восстановленной информационной последовательности (АВИП), номер которой на T1=4-1=3 меньше номера очередной части этой последовательности. Следовательно, с задержкой декодирования передают получателю первую часть восстановленной информационной последовательности вида "00". После этого получают очередной бит Пр.П и выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные биты Пр.П.
Детально опишем действия совместного арифметического и помехоустойчивого декодирования на приемной стороне.
Способы разделения текущего интервала арифметического декодирования длиною DD>2 каждой АПП на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа этой последовательности идентичны способам разделения текущего интервала арифметического кодирования длиною D>2 на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа. Верхнюю границу текущего подинтервала декодирования нулевого символа обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы текущего интервала декодирования LL до значения Q<2 исключительно, а текущий подинтервал декодирования единичного символа простирается от значения QQ включительно до верхней границы текущего интервала декодирования HH исключительно. Например, в начальный момент времени t=0 имеется единственная АПП с предварительно установленным нулевым значением метрики (М=0), совпадающая с начальной принятой последовательности вида "0100 0000", для нее значение нижней границы текущего интервала декодирования равно LL[0]=0, а значение верхней границы текущего интервала декодирования - HH[0]=255, как показано на фиг. 11 в первой строке при t=0. Длина текущего интервала арифметического декодирования АПП DD=255.
0
1
Для разделения текущего интервала арифметического декодирования каждой АПП на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа подсчитывают текущее число нулевых символов NN и текущее число единичных символов NN соответствующей ей АВИП.
Например, в начальный момент при t=0 текущее число нулевых символов АВИП установлено в значение 1, и текущее число единичных символов АВИП установлено в значение 1. Например, как показано на фиг. 11 в первой строке при t=0 для АПП вида "0100 0000" указано единичное число нулевых символов АВИП (графа NN0) и единичное число единичных символов этой же АВИП (графа NN1). В графе NN указывается общее число нулевых и единичных символов АВИП.
0
0
0
0
1
1
1
1
0
1
Затем вычисляют текущую вероятность нулевых символов АВИП pp[t] по правилу: pp[t]=NN[t]/(NN[t]+NN[t]) и текущую вероятность единичных символов АВИП pp[t] по правилу: pp[t]=NN[t]/(NN[t]+NN[t]). Например, как показано на фиг. 11 в первой строке при t=0 указано значение начальной вероятности нулевых символов АВИП (графа рр0) и значение начальной вероятности единичных символов АВИП (графа pp1), где начальные значения равны 0,5.
1
1
1
0
0
1
1
0
Длину текущего подинтервала декодирования единичных символов АПП DD[t] определяют по формуле вида DD[t]=DD[t]×pp[t], а длину текущего подинтервала декодирования нулевых символов АПП DD[t] определяют по формуле вида DD[t]=DD[t]-DD[t]. Например, длина начального подинтервала единичных символов АПП DD[0] имеет десятичное значение 128 или 1000 0000 в двоичном представлении, а длина начального подинтервала нулевых символов АПП DD[0] имеет десятичное значение 127 или 0111 1111 в двоичном представлении. Подинтервал единичных символов расположен сверху подинтервала нулевых символов, как показано, например, на фиг. 11. Верхнюю границу подинтервала нулевых символов АПП обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы интервала декодирования арифметического декодирования АПП включительно до значения QQ исключительно, а подинтервал единичных символов простирается от значения QQ включительно до верхней границы интервала декодирования арифметического декодирования АПП исключительно. Начальное значение QQ имеет десятичное значение 127, как показано на фиг. 11 в первой строке при t=0.
Для каждой АПП формируют продолжение последовательности в виде нулевого символа и продолжение в виде единичного символа. Например, АПП с продолжением в виде нулевого символа получает вид "0100 0000 0", как показано на фиг. 11, а АПП с продолжением в виде единичного символа получает вид "0100 0000 1", как показано на фиг. 12.
После формирования продолжения последовательности вычисляют значение метрики продолжения в виде нулевого символа и значение метрики продолжения в виде единичного символа относительно очередного бита принятой последовательности, при этом значение метрики продолжения в виде нулевого символа относительно очередного бита принятой последовательности вычисляют как нулевое значение, если очередной бит очередной части принятой последовательности является нулевым битом, иначе вычисляют как единичное значение, а также значение метрики продолжения в виде единичного символа относительно очередного бита принятой последовательности вычисляют как нулевое значение, если очередной бит принятой последовательности является единичным битом, иначе вычисляют как единичное значение. Например, как показано на фиг. 11, очередной бит Пр.П, следующий после считывания восьми битов начального пути декодирования, имеет нулевое значение. Поэтому относительно этого бита метрика продолжения последовательности в виде нулевого символа имеет нулевое значение, а метрика продолжения последовательности в виде единичного символа имеет единичное значение, как показано на фиг. 10.
Затем для каждой АПП с ее продолжением последовательности вычисляют значение его метрики, для чего суммируют значения метрики данной последовательности и метрики ее продолжения последовательности. Например, метрика АПП "0100 0000 0" с продолжением в виде нулевого символа получает нулевое значение (М=0), а метрика АПП "0100 0000 1" с продолжением в виде единичного символа получает единичное значение (М=1).
Способы арифметического декодирования каждой АПП с ее продолжением последовательности в очередные части соответствующей ей альтернативной декодированной последовательности (АДП) известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном декодировании АПП с ее продолжением в соответствии с текущими значениями интервала декодирования арифметического декодирования этой последовательности и текущими значениями вероятности декодируемых нулевых символов и единичных символов соответствующей ей АВИП.
0
1
Примерный вид арифметического декодирования АПП с ее продолжением "0100 0000 0" в символы первой части соответствующей ей АДП показан на фиг. 11. Первоначально на вход арифметического декодирования считаны первые по очереди 8 бит вида "0100 0000", что соответствует десятичному числу 64. Текущие считываемые биты (сч.) показаны во втором столбце, в третьем столбце этой же таблицы (Пр. поcл.) на фиг. 11 показано текущее значение принятой последовательности. Для декодирования текущее значение Пр.П сравнивают с границами текущего значения (первоначально начального значения) подинтервала декодирования нулевых символов АПП DD[0], находящимися, например, в пределах от 0 до 127, и с границами текущего значения (первоначально начального значения) подинтервала декодирования единичных символов АПП DD[0], находящимися, например, в пределах от 127 до 255. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение принятой последовательности, принимают решение о значении текущего символа альтернативной декодированной последовательности (Дек. сим.), указываемых в правой графе фиг. 11.
0
1
Например, так как текущее значение принятой последовательности оказалось меньше значения QQ(64<127), то первый декодированный символ является нулевым и следующие границы интервала декодирования устанавливают соответствующими границам значения подинтервала декодирования нулевых символов данной АПП DD[0]. В результате декодирования первого символа устанавливают нижнее значение интервала декодирования арифметического декодирования LL[1] равным предыдущему значению LL[0], например, LL[1]=0, а верхнее значение интервала декодирования арифметического декодирования HH[1] - равным значению QQ, например, HH[1]=127, как показано на фиг. 11 во второй строке при t=1.
0
0
0
1
1
1
0
1
После декодирования каждого символа пересчитывают текущее значение вероятности нулевых символов АВИП и текущее значение вероятности единичных символов этой же последовательности, например, после декодирования первого символа, являющегося нулевым, по формуле вида pp[1]=NN[1]/(NN[1]+NN[1])=2/3 и по формуле вида pp[1]=NN[1]/(NN[1]+NN[1])=1/3, соответственно.
После каждого изменения состояния арифметического декодирования (Сост. декодирования) самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения HH, например, при t=1 значение LL вида "0000 0000" и значение HH вида "0111 1111", соответственно. При их совпадении выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL и HH удаляют и двоичные символы двоичных представлений значений LL и HH сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Одновременно с этим, самый левый бит текущего значения принятой последовательности удаляют и двоичные символы этой последовательности сдвигают справа налево на один разряд и справа к ним дописывают следующий считанный двоичный символ принятой последовательности. Как было описано выше, следующим считанным двоичным символом является девятый по счету символ принятой последовательности, имеющий нулевое значение. Со считыванием этого бита метрика данной альтернативной принятой последовательности с ее продолжением вида "0010 1110 0" сохранила нулевое значение (М=0), как показано на фиг. 10. С учетом считанного двоичного символа, текущее значение принятой последовательности получило десятичное значение 128 и двоичное представление "1000 0000".
Переменная сохранила десятичное значение 0, а HH - получила десятичное значение 254 и двоичное представление "1111 1110". Повторно самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения HH, и если они снова совпадают, то выполняют повторную нормализацию идентичным образом и т.д.
Таким же образом выполняют арифметическое декодирование АПП с продолжением последовательности до тех пор, пока не будут декодировано k бит очередной (в данном случае первой части) части соответствующей ей АВИП. В результате арифметического декодирования АПП с продолжением последовательности в виде нулевого символа вида "0100 0000 0", показанной на фиг. 7(б), декодируют, например, два символа первой части соответствующей ей АДП, имеющей вид "00", как показано на фиг. 7(в) и на фиг. 11.
0
0
0
1
1
1
0
1
Из очередной части АДП выделяют очередную часть альтернативной восстановленной информационной последовательности (АВИП). Очередная часть АВИП совпадает с очередной частью АДП. Например, из первой части АДП вида "00", соответствующей АПП с продолжением последовательности вида "0100 0000 0", выделяют первую часть АВИП вида "00", соответствующую той же АПП с продолжением последовательности вида "0100 0000 0", как показано на фиг. 7(г). Соответственно, после выделения первой части АВИП вида "00", соответствующей АПП с продолжением последовательности вида "0100 0000 0", текущее значение вероятности нулевых символов этой АВИП равно рр[2]=NN[2]/(NN[2]+NN[2])=3/4, и текущее значение вероятности единичных символов этой же последовательности равно рр[2]=NN[2]/(NN[2]+NN[2])=1/4.
Для АПП с продолжением в виде единичного символа вида "0100 0000 1", показанной на фиг. 7(д), арифметическое декодирование первой части соответствующей ей АДП показано на фиг. 12, вид "00" первой части соответствующей ей АДП показан на фиг. 7(e), а вид "00" первой части соответствующей ей АВИП показан на фиг. 7(ж). Метрика АПП "0100 0000 1" с продолжением в виде единичного символа имеет единичное значение (М=1).
β
β
β
После выделения k-го бита очередной части АВИП разделяют текущий интервал арифметического декодирования длиною DD каждой альтернативной принятой последовательности на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, из которых выделяют текущий разрешенный подинтервал декодирования длиною DD≥1, длину которого выбирают как DD=β⋅DD. Данные действия на приемной стороне аналогичны действиям на передающей стороне по разделению текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, из которых выделяют текущий разрешенный подинтервал кодирования длиною D≥1.
0
1
β
β
Например, после выделения второго бита при k=2 первой части АВИП, соответствующей АПП с продолжением последовательности вида "0100 0000 0" текущий интервал арифметического декодирования данной АПП находится в пределах от LL[2]=0 до HH[2]=169, и его длина составляет DD=169. В соответствии с текущим значением вероятности нулевых символов АВИП, соответствующей этой АПП, равным pp[2]=3/4, и текущим значением вероятности единичных символов этой же АВИП, равным pp[2]=1/4, текущий интервал арифметического декодирования данной АПП разделяют на текущий подинтервал декодирования нулевого символа от LL[2]=0 до QQ=127 и на текущий подинтервал декодирования единичного символа от QQ=127 до HH[2]=169, как показано в пятой строке фиг. 11. Из этих подинтервалов выделяют текущий разрешенный подинтервал декодирования длиною DD[2]=0,4⋅DD[2]=0,4⋅169=78. Например, пропорционально длине текущего подинтервала декодирования нулевого символа из него в текущий разрешенный подинтервал декодирования выделяют 0,4⋅127=51 единиц длины, и пропорционально длине текущего подинтервала декодирования единичного символа из него в текущий разрешенный подинтервал декодирования выделяют 0,4⋅42=17 единиц длины. В результате текущий разрешенный подинтервал декодирования DD[2] простирается от значения LLk[2]=127-51=76 до значения HHk[2]=127+17=154, как показано в пятой строке (выделен, разреш. подинт.) фиг. 11.
β
Устанавливают текущий интервал арифметического декодирования каждой АПП равным ее текущему разрешенному подинтервалу декодирования длиною DD, если текущее значение принятой последовательности находится в пределах текущего разрешенного подинтервала декодирования АПП, то запоминают очередные части АВИП, соответствующей этой последовательности, иначе стирают данную АПП с ее продолжением последовательности.
Например, после выделения второго бита при k=2 первой части АВИП, соответствующей АПП с продолжением последовательности вида "0100 0000 0", текущий интервал арифметического декодирования данной АПП устанавливают от значения LLk[2]=76 до значения HHk[2]=154, как показано в пятой строке (выделен, разреш. подинт.) фиг. 11. Текущее значение принятой последовательности в этот момент времени равно 128, как указано в столбце "Прин. послед". Сравнивают текущее значение принятой последовательности с нижним значением и верхним значением текущего разрешенного подинтервала декодирования данной АПП. Текущее значение принятой последовательности находится в пределах текущего разрешенного подинтервала декодирования, так как выполняется соотношение LLk[t]≤ Прин. послед. ≤HHk[t]. Запоминают очередные части АВИП, соответствующей этой последовательности, то есть запоминают первую часть АВИП вида "00" для АПП с продолжением последовательности вида "0100 0000 0".
R
Аналогичным образом для каждой АПП устанавливают ее текущий интервал арифметического декодирования и проверяют принадлежность текущего значения принятой последовательности текущему разрешенному подинтервалу декодирования данной АПП. Отметим, что текущие разрешенные подинтервалы декодирования разных АПП, как правило, различаются после приема не менее 2N бит принятой последовательности. Если текущее значение принятой последовательности не находится в пределах текущего разрешенного подинтервала декодирования АПП, то это означает, что такая АПП не может быть сформирована на передающей стороне и она подлежит стиранию.
Затем сравнивают между собой значения метрики АПП с их продолжениями последовательности и выбирают из них не более предельного числа Z АПП, имеющих наименьшие значения метрики. Данные способы известны и описаны, например, в книге М. Сибуя, Т. Ямамото "Алгоритмы обработки данных". - М., Мир, 1986, стр. 122-134, и заключаются в поочередном сравнении между собой значений метрики АПП с их продолжениями, сортировке последовательностей по мере возрастания значений метрики и выборе среди отсортированных последовательностей первых Z последовательностей с наименьшими значениями метрики. Например, после считывания и декодирования текущего, девятого по счету, бита принятой последовательности, АПП с их продолжениями насчитывается две, поэтому при установленном значении Z=13 выбирают обе рассмотренные выше альтернативные принятые последовательности с их продолжениями.
После считывания двенадцатого по счету очередного бита принятой последовательности число АПП с их продолжениями насчитывают 16 и среди них выбирают Z=13 АПП с их продолжениями, при этом одна выбранная последовательность имеет метрику М=0, четыре - М=1, шесть - М=2 и две М=3. Стерты одна последовательность с метрикой М=4 и две с метрикой М=3. Факт стирания невыбранной альтернативной принятой последовательности с ее продолжениям отмечают символом "X" на фиг. 10.
В выбранные АПП с их продолжениями дописывают соответствующие им продолжения, для этих АПП запоминают очередные части соответствующих им АВИП и значения метрики. Например, после считывания девятого по счету очередного бита принятой последовательности сохранены АПП вида "00101110 0" с соответствующей ей АВИП вида "00" и метрикой М=0, а также АПП вида "00101110 1" с соответствующей ей АВИП вида "00" и метрикой М=1.
Если номер очередной части АВИП меньше величины задержки декодирования T очередных частей ВИП, то выполняют перечисленные действия на приемной стороне. Например, после считывания девятого по счету очередного бита принятой последовательности из АПП вида "0100 0000 0" получены первая и вторая части соответствующей ей АВИП вида "00" и "01", а из АПП вида "0100 0000 1" получены первая и вторая части соответствующей ей АВИП вида "00" и "01", как показано на фиг. 7(г) и фиг. 7(ж), номера частей этих АВИП меньше величины задержки декодирования T=4 очередных частей ВИП. В этом случае считывают очередной бит принятой последовательности и т.д.
Например, при приеме первых пятнадцати бит принятой последовательности декодирование на приемной стороне для АПП вида "0100 0000 0001 111" показано на фиг. 13. Данная АПП в процессе декодирования сохраняет значение метрики М=0, то есть оценивается как последовательность, с наибольшей вероятностью совпадающая с кодированной последовательностью, сформированной на передающей стороне. Из этой АПП, вид которой показан на фиг. 7(з), декодированы первые три части АДП вида "00", "01", "00", как показано на фиг. 7(и), из которых выделены первые три части АВИП такого же вида, как показано на фиг. 7(к). После выделения второго бита третьей части АВИП текущее значение принятой последовательности, равное 15, сравнивают с нижним и верхним значением текущего интервала декодирования АПП, равными 80 и 126, соответственно, как показано в предпоследней строке фиг. 13. Выявлено, что текущее значение принятой последовательности находится вне пределов текущего интервала декодирования АПП, следовательно, данная АПП не может быть сформирована на передающей стороне и подлежит стиранию.
Декодирование АПП вида "0100 0000 1101 1111 0" показано на фиг. 14. Как показано на фиг. 10, данная АПП является одной из четырех АПП, сохранившихся из всех АПП при приеме первых семнадцати бит принятой последовательности. Из этой АПП, вид которой показан на фиг. 7(л), декодированы первые четыре части АДП вида "00", "01", "00", "01", как показано на фиг. 7(м), из которых выделены первые четыре части АВИП такого же вида, как показано на фиг. 7(н).
Так как номер четвертой части альтернативной восстановленной информационной последовательности, соответствующей этой АПП, сравнялся с величиной задержки декодирования T=4 очередных частей ВИП, то сравнивают между собой значения метрики альтернативных принятых последовательностей и выбирают из них последовательность с наименьшим значением метрики. Как показано на фиг. 10, среди сохранившихся АПП одна АПП имеет значение метрики М=4, две АПП - М=3 и рассматриваемая АПП имеет наименьшее значением метрики М=2. Поэтому выбирают АПП вида "0100 0000 1101 1111 0".
В качестве очередной части восстановленной информационной последовательности передают получателю соответствующую выбранной АПП часть альтернативной восстановленной информационной последовательности, номер которой на (T-1) меньше номера очередной части этой АВИП. Очередной частью АВИП, соответствующей выбранной АПП, является четвертая часть АВИП, поэтому очередной (в данный момент первой) частью восстановленной информационной последовательности является первая часть данной АВИП, так как на (4-1) меньше четвертого номера является первый номер. Таким образом, первая часть восстановленной информационной последовательности имеет вид "00".
Затем по мере считывания и декодирования очередных битов принятой последовательности передают получателю следующие части восстановленной информационной последовательности. Из сравнения первых четырех частей ИП, показанных на фиг. 6(a), и первых четырех частей ВИП, показанных на фиг. 7(н), видно, что обеспечено исправление двукратной ошибки канала передачи.
Проверка теоретических предпосылок заявленного способа совместного арифметического и помехоустойчивого кодирования и декодирования выполнялась путем его аналитических исследований.
Было выполнено совместное арифметическое и помехоустойчивое кодирование и декодирование очередных частей длиной k=2 бит избыточной информационной последовательности общей длиной 1024 бит с использованием способа-прототипа, результаты показаны на фиг. 15. При значении коэффициента помехоустойчивости β=0,4 оценивалась вероятность исправления двух и трех кратных ошибок при задержке декодирования T=10 и T=17 очередных частей восстановленной информационной последовательности при использовании 10≤Z≤40 альтернативных принятых последовательностей.
исправл
N
Максимальная вероятность исправления ошибок произвольной кратности на длине T очередных частей принятой последовательности при установленном значении коэффициента помехоустойчивости β оценивается по формуле Р=1-(1-β). При T=10 максимальная вероятность исправления ошибок произвольной кратности равна 0,99395, а при T=17-0,99983. В ходе имитационного моделирования на длине Т случайным образом генерировались различные комбинации двухкратных и трехкратных ошибок передачи. При исправлении двухкратных ошибок на длине T=10 при использовании Z=10 альтернативных принятых последовательностей достигнута практическая вероятность исправления 0,91, при использовании Z=20-0.98, а при исправлении трехкратных ошибок на длине T=10 при использовании Z=10 альтернативных принятых последовательностей достигнута практическая вероятность исправления 0,88, а при использовании Z=40-0.97. Соответственно, при исправлении двухкратных ошибок на длине T=17 при использовании Z=10 альтернативных принятых последовательностей достигнута практическая вероятность исправления 0,94, при использовании Z=20-0.97, а при исправлении трехкратных ошибок на длине T=17 при использовании Z=10 альтернативных принятых последовательностей достигнута практическая вероятность исправления 0,91, а при использовании Z=40-0.998. Выявлено, что при увеличении задержки декодирования T очередных частей восстановленной информационной последовательности, числа Z альтернативных принятых последовательностей и величины коэффициента помехоустойчивости β обеспечивается повышение помехоустойчивости передачи очередных частей кодированной последовательности при воздействии многократных ошибок передачи.
Проведенные исследования подтверждают, что при использовании предлагаемого способа совместного арифметического и помехоустойчивого кодирования и декодирования обеспечивается повышение помехоустойчивости передачи очередных частей кодированной последовательности при воздействии многократных ошибок передачи.