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

Заявленное техническое решение относится к области электросвязи и информационных технологий, а именно к технике сжатия и восстановления избыточной двоичной информации и ее помехоустойчивого кодирования и декодирования при передаче информации по каналам с ошибками.
Заявленное изобретение может быть использовано для обеспечения достоверности избыточной двоичной информации, передаваемой по каналам с ошибками.
Известен способ адаптивного помехоустойчивого кодирования и декодирования по патенту РФ 2375824 МПК H04 L1/20 (2006.01) от 10.12.2009, заключающийся в том, что на передающей стороне исходную информацию кодируют помехоустойчивым кодом с переменными параметрами, далее помехоустойчивый код передают в канал связи, на приемной стороне помехоустойчивый код декодируют с обнаружением и исправлением ошибок в зависимости от корректирующей способности выбранного кода, по результатам декодирования помехоустойчивого кода оценивают качество канала связи и выбирают переменные параметры помехоустойчивого кода, обеспечивающие заданную вероятность правильного приема помехоустойчивого кода, и далее эти параметры помехоустойчивого кода сообщают на передающую сторону, отличающийся тем, что на приемной стороне по результатам декодирования помехоустойчивого кода рассчитывают начальную величину избыточности помехоустойчивого кода, обеспечивающую заданную вероятность правильного приема помехоустойчивого кода, оценивают вероятность правильного приема помехоустойчивого кода с выбранными параметрами, вычисляют величину отклонения полученной вероятности правильного приема помехоустойчивого кода от заданной вероятности правильного приема кода и в зависимости от величины этого отклонения корректируют величину избыточности помехоустойчивого кода, которую передают на передающую сторону, где формируют помехоустойчивый код с полученной избыточностью.
Недостатком указанного аналога является неэффективное использование пропускной способности канала передачи, вызванное отсутствием сжатия избыточной двоичной информации при обмене данными по каналам передачи с ошибками.
Известен также способ совместного сжатия и помехоустойчивого кодирования и декодирования речевых сообщений, описанный, например, в книге С.Н. Кириллов, В.Т. Дмитриев, Д.Е. Крысяев, С.С. Попов "Исследование качества передаваемой речевой информации при различном сочетании алгоритмов кодирования источника и канала связи в условиях воздействия помех". - Рязань, Вестник РГРТУ, Выпуск 23, 2008. Данный способ заключается в том, что предварительно формируют множество способов сжатия речевого сигнала, таких как импульсно-кодовая модуляция, адаптивная дельта-модуляция, адаптивная дифференциальная импульсно-кодовая модуляция, и множество способов помехоустойчивого кодирования, таких как кодирование Хэмминга, кодирование Боуз-Чоудхури-Хоквингема, на передающей стороне от отправителя получают очередную часть речевого сигнала длиною речевая фраза, который преобразуют в сжатую двоичную последовательность с помощью одного из способов сжатия речевого сигнала, выполняют помехоустойчивое кодирование сжатой двоичной последовательности с помощью одного из способов помехоустойчивого кодирования, передают на приемную сторону по каналу прямой связи очередную часть кодированной последовательности вместе с информацией об использованном способе сжатия речевого сигнала и способе помехоустойчивого кодирования, на приемной стороне получают очередную часть принятой последовательности, очередную часть принятой последовательности последовательно декодируют с использованием соответствующих способа помехоустойчивого декодирования и способа восстановления речевого сигнала, вычисляют оценку качества восстановленного речевого сигнала и полученную оценку сравнивают с пороговым значением качества, если вычисленная оценка качества восстановленного речевого сигнала не хуже предварительно установленного порогового значения качества, то передают получателю очередную часть восстановленной информационной последовательности и передающей стороне от отправителя получают очередную часть речевого сигнала и выполняют последующие действия, иначе передают по каналу обратной связи требование изменить способ сжатия речевого сигнала и способ помехоустойчивого кодирования, и выполняют последующие действия.
Недостатком указанного аналога является большая задержка передачи сообщений по каналу связи, вызванная необходимостью подбора подходящих способа сжатия речевого сигнала и способа помехоустойчивого кодирования.
Наиболее близким по своей технической сущности к заявленному способу совместного арифметического и помехоустойчивого кодирования и декодирования является способ совместного арифметического и помехоустойчивого кодирования и декодирования по патенту США 6892343 МПК H04 M13/00 (2006.01) от 10.05.2005. Способ - прототип совместного арифметического и помехоустойчивого кодирования и декодирования заключается в том, что предварительно на передающей стороне устанавливают начальный интервал арифметического кодирования и на приемной стороне соответствующий ему начальный интервал арифметического декодирования, на передающей стороне от источника информации принимают очередную часть информационной последовательности длиной k≥1 бит, разделяют текущий интервал арифметического кодирования длиною D>2 на текущий подинтервал кодирования нулевого символа D0 и на текущий подинтервал кодирования единичного символа D1, из предварительно сформированного множества выбирают проверочные символы длиной r≥1 бит и формируют очередную часть помехоустойчивой последовательности из очередной части информационной последовательности и выбранных проверочных символов, выполняют арифметическое кодирование очередной части помехоустойчивой последовательности в очередную часть кодированной последовательности, преобразуют очередную часть кодированной последовательности в очередную часть модулированной последовательности, передают очередную часть модулированной последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные части информационной последовательности, на приемной стороне принимают очередную часть последовательности, преобразуют ее в двоичную последовательность, которую запоминают, разделяют текущий интервал арифметического декодирования длиною DD>2 на текущий подинтервал декодирования нулевого символа DD0 и на текущий подинтервал декодирования единичного символа DD1, запомненные очередные части принятой последовательности арифметически декодируют в очередные части декодированной последовательности, из которых выделяют очередные части восстановленной информационной последовательности и декодированные проверочные символы, если декодированные проверочные символы принадлежат предварительно сформированному множеству проверочных символов, то делают вывод об отсутствии ошибок передачи и передают очередную часть восстановленной информационной последовательности, иначе поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности и выполняют их арифметическое декодирование до достижения вывода об отсутствии ошибок передачи, выполняют перечисленные действия на приемной стороне до тех пор, пока на приемной стороне поступают очередные части принятой последовательности.
Особенностью способа-прототипа является то, что на передающей стороне выполняют выбор проверочных символов, а затем сжатие очередных частей информационной последовательности и проверочных символов путем арифметического кодирования, а на приемной стороне после арифметического декодирования обнаруживают ошибки передачи при их наличии, а при их обнаружении методом проб и ошибок выполняют их исправление. Способ-прототип совместного арифметического и помехоустойчивого кодирования и декодирования обеспечивает возможность обнаружения и исправления ошибок передачи.
W
Однако в данном способе-прототипе совместного арифметического и помехоустойчивого кодирования и декодирования информационной последовательности исправление ошибок передачи выполняют методом перебора, поочередно инвертируя один или несколько битов в запомненных очередных частях принятой последовательности и выполняя их арифметическое декодирование до достижения вывода об исправлении этих ошибок с использованием проверочных символов. При длине N бит запомненных очередных частей принятой последовательности и числе W исправляемых ошибок это требует параллельной работы порядка N/2 арифметических декодеров с соответствующим числом устройств обнаружения ошибок. При арифметическом декодировании сжатых избыточных двоичных последовательностей наличие ошибок передачи выявляется при длине запомненных очередных частях принятой последовательности вплоть до десятков бит и более. Поэтому в данном способе-прототипе совместного арифметического и помехоустойчивого кодирования и декодирования исправление ошибок передачи при кратности ошибок более одной требует использования многих тысяч арифметических декодеров с соответствующим числом устройств обнаружения ошибок, что является практически нереализуемым.
Таким образом, недостатком ближайшего аналога (прототипа) совместного арифметического и помехоустойчивого кодирования и декодирования информационной последовательности является низкая помехоустойчивость передачи очередных частей кодированной последовательности, обусловленная практической невозможностью исправления ошибок передачи при кратности ошибок более одной.
Техническим результатом заявляемого решения является разработка способа совместного арифметического и помехоустойчивого кодирования и декодирования, обеспечивающего повышение помехоустойчивости передачи очередных частей кодированной последовательности при воздействии многократных ошибок передачи.
Указанный технический результат в заявляемом способе совместного арифметического и помехоустойчивого кодирования и декодирования достигается тем, что в известном способе совместного арифметического и помехоустойчивого кодирования и декодирования, заключающимся в том, что предварительно на передающей стороне устанавливают начальный интервал арифметического кодирования и на приемной стороне соответствующий ему начальный интервал арифметического декодирования, на передающей стороне от источника информационной последовательности принимают очередную часть информационной последовательности длиной k≥1 бит, разделяют текущий интервал арифметического кодирования длиной D>2 на текущий подинтервал кодирования нулевого символа длиной D0 и на текущий подинтервал кодирования единичного символа длиной D1, выполняют арифметическое кодирование очередной части последовательности в очередную часть кодированной последовательности, передают очередную часть последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные части информационной последовательности, на приемной стороне принимают последовательность, разделяют текущий интервал арифметического декодирования длиною DD>2 на текущий подинтервал декодирования нулевого символа DD0 и на текущий подинтервал декодирования единичного символа DD1, арифметически декодируют очередные части принятой последовательности в очередные части последовательности, выполняют перечисленные действия на приемной стороне до тех пор, пока поступает принятая последовательность, передают получателю восстановленную информационную последовательность, дополнительно предварительно устанавливают предельное число Z≥2 альтернативных принятых последовательностей и значение метрики альтернативных принятых последовательностей в нулевое значение.
a
a
a
a
a
a
a
a
a
a
а
m
m
На передающей стороне в зависимости от m≥1 ранее кодированных символов информационной символов из текущего подинтервала арифметического кодирования нулевого символа длиной D0≥2 выделяют текущий разрешенный подинтервал кодирования нулевого символа длиной D0, где 1≤D0<D0, и из текущего подинтервала кодирования единичного символа длиной D1≥2 выделяют текущий разрешенный подинтервал кодирования единичного символа длиной D1, где 1≤D1<D1. Длину D0 текущего разрешенного подинтервала кодирования нулевого символа выбирают как D0=⋅D0, а длину D1 текущего разрешенного подинтервала кодирования единичного символа выбирают как D1=⋅D1, где коэффициент обнаружения ошибок а выбирают в пределах 0<<1.
В соответствии с выделенными текущими разрешенными подинтервалами кодирования выполняют арифметическое кодирование очередной части информационной последовательности в очередную часть кодированной последовательности, которую передают на приемную сторону.
a
a
a
a
a
a
a
a
a
a
m
m
На приемной стороне принимают очередной бит последовательности, текущий интервал арифметического декодирования длиной DD каждой альтернативной принятой последовательности разделяют на текущий подинтервал декодирования нулевого символа длиной DD0≥2 и на текущий подинтервал декодирования единичного символа длиной DD1≥2, из которых в зависимости от m символов восстановленной информационной последовательности каждой альтернативной принятой последовательности выделяют текущий разрешенный подинтервал декодирования нулевого символа длиной DD0, где 1≤DD0<DD0, и, соответственно, текущий разрешенный подинтервал декодирования единичного символа длиной DD1, где 1≤DD1<DD1. Длину DD0 текущего разрешенного подинтервала декодирования нулевого символа выбирают как DD0=⋅DD0, а длину DD1 текущего разрешенного подинтервала декодирования единичного символа выбирают как DD1=⋅DD1.
Если текущее значение альтернативной принятой последовательности не находится в пределах текущего разрешенного подинтервала декодирования нулевого символа или текущего разрешенного подинтервала декодирования единичного символа этой альтернативной принятой последовательности, то стирают данную альтернативную принятую последовательность, иначе арифметически декодируют альтернативную принятую последовательность в соответствии с текущими разрешенными подинтервалами декодирования в очередные части соответствующей ей альтернативной восстановленной последовательности.
Для каждой альтернативной принятой последовательности формируют продолжение последовательности в виде нулевого символа и продолжение последовательности в виде единичного символа, устанавливают значение метрики продолжения последовательности в виде нулевого символа и значение метрики продолжения последовательности в виде единичного символа относительно очередного бита принятой последовательности. Значение метрики продолжения последовательности в виде нулевого символа относительно очередного бита принятой последовательности устанавливают в нулевое значение, если очередной бит принятой последовательности является нулевым битом, иначе устанавливают в единичное значение. Значение метрики продолжения последовательности в виде единичного символа относительно очередного бита принятой последовательности устанавливают в нулевое значение, если очередной бит принятой последовательности является единичным битом, иначе устанавливают в единичное значение.
Для каждой альтернативной принятой последовательности с ее продолжением последовательности вычисляют значение ее метрики, для чего суммируют значения метрики данной последовательности и метрики ее продолжения последовательности, сравнивают между собой значения метрики альтернативных принятых последовательностей с их продолжениями последовательности и выбирают из них не более предельного числа Z альтернативных принятых последовательностей, имеющих наименьшие значения метрики, которые дополняют соответствующими им продолжениями последовательности, для этих альтернативных принятых последовательностей запоминают очередные части соответствующих им альтернативных восстановленных информационных последовательностей и значения метрики.
Выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные биты принятой последовательности, сравнивают между собой значения метрики альтернативных принятых последовательностей и выбирают из них последовательность с наименьшим значением метрики, после чего передают получателю в качестве восстановленной информационной последовательности соответствующую выбранной альтернативной принятой последовательности альтернативную восстановленную информационную последовательность.
а
а
а
В предлагаемой совокупности действий на передающей стороне при арифметическом кодировании очередной части информационной последовательности в очередную часть кодированной последовательности последнюю формируют в соответствии с текущими разрешенными подинтервалами кодирования, а на приемной стороне при декодировании очередных частей принятой последовательности стирают те альтернативные принятые последовательности, которые не могут быть сформированы на передающей стороне в соответствии с текущими разрешенными подинтервалами, среди оставшихся сохраняют и продолжают ограниченное число Z альтернативных принятых последовательностей с их продолжениями последовательности, имеющих наименьшие значения метрики, и после приема всей последовательности среди лучших по критерию метрики продолжаемых альтернативных принятых последовательностей выбирают последовательность с наименьшим значением метрики, которая с наибольшей вероятностью совпадает со сформированной на передающей стороне кодированной последовательностью. Тем самым выполняют исправление ошибок канала передачи, причем кратность исправленных ошибок в принятой последовательности соответствует значению метрики выбранной альтернативной принятой последовательности. Данный способ декодирования относится к классу методов декодирования сообщения в целом, которые теоретически способны достичь предельно высокой помехоустойчивости передачи сообщений. Благодаря тому, что при декодировании очередных битов принятой последовательности стирают альтернативные принятые последовательности, которые не обеспечивают исправление произошедших ошибок канала передачи, и продолжают ограниченное число Z нестертых альтернативных принятых последовательностей с их продолжениями последовательности, которые обеспечивают максимизацию вероятности исправления ошибок передачи, обеспечивается возможность исправления многократных ошибок передачи путем декодирования ограниченного числа альтернативных принятых последовательностей. Способность обнаруживать и исправлять многократные ошибки канала передачи увеличивается при уменьшении значения коэффициента обнаружения ошибок  и увеличении предельного числа Z альтернативных принятых последовательностей. В заявленном способе совместного арифметического и помехоустойчивого кодирования и декодирования коэффициент обнаружения ошибок , выбираемый в пределах 0<<1, является эквивалентом скорости помехоустойчивого кода , где k≥1 есть длина очередной части информационной последовательности, а n=k+r есть длина очередной части помехоустойчивой последовательности, состоящей из k информационных символов и из r≥1 проверочных символов. Однако в заявленном способе за счет совместности выполнения действий арифметического и помехоустойчивого кодирования и декодирования проверочные символы не используются.
Поэтому указанная новая совокупность действий при выполнении совместного арифметического и помехоустойчивого кодирования и декодирования информационной последовательности позволяет обеспечить повышение помехоустойчивости передачи очередных частей кодированной последовательности при воздействии многократных ошибок передачи.
Заявленный способ поясняется чертежами, на которых показаны:
- на фиг. 1 - общая схема совместного арифметического и помехоустойчивого кодирования и декодирования;
- на фиг. 2 - схема блока декодирования 8;
- на фиг. 3 - алгоритм совместного арифметического и помехоустойчивого кодирования на передающей стороне;
- на фиг. 4 - таблица состояний совместного арифметического и помехоустойчивого кодирования первых семнадцати очередных частей информационной последовательности;
- на фиг. 5 - временные диаграммы совместного арифметического и помехоустойчивого кодирования первых двух очередных частей информационной последовательности;
- на фиг. 6 - выбор разрешенных подинтервалов кодирования в зависимости от m≥1 ранее кодированных символов информационной последовательности;
- на фиг. 7 - временные диаграммы совместного арифметического и помехоустойчивого кодирования первых 17 очередных частей информационной последовательности;
- на фиг. 8 - временные диаграммы совместного арифметического и помехоустойчивого декодирования первых 17 битов принятой последовательности на приемной стороне;
- на фиг. 9 - алгоритм совместного арифметического и помехоустойчивого декодирования на приемной стороне;
- на фиг. 10 - представление альтернативных принятых последовательностей в виде древовидной структуры;
- на фиг. 11 - примерный вид выбираемых не более Z=21 альтернативных принятых последовательностей;
-на фиг. 12 - таблица состояний декодирования альтернативной принятой последовательности вида "0001 1110 0";
- на фиг. 13 - таблица состояний декодирования альтернативной принятой последовательности вида "0001 1110 1";
- на фиг. 14 - таблица состояний декодирования альтернативной принятой последовательности вида "0001 1110 1100 0110 1";
- на фиг. 15 - таблица состояний декодирования альтернативной принятой последовательности вида "0001 1110 0000 0110 1".
Реализация заявленного способа представлена на примере системы совместного арифметического и помехоустойчивого кодирования и декодирования, показанной на фиг. 1. На передающей стороне выполняют совместное арифметическое и помехоустойчивое кодирование очередных частей информационной последовательности (ИП), а на приемной стороне - совместное арифметическое и помехоустойчивое декодирование принятой последовательности с исправлением ошибок канала передачи.
На передающей стороне формирователь текущего интервала кодирования 1 формирует текущий интервал арифметического кодирования в зависимости от принимаемой информационной последовательности. Из текущего интервала арифметического кодирования формирователь текущего нулевого подинтервала кодирования 2 формирует текущий подинтервал кодирования нулевого символа и, соответственно, формирователь текущего единичного подинтервала кодирования 3 формирует текущий подинтервал кодирования единичного символа. При получении от отправителя нулевого символа очередной части информационной последовательности увеличивается текущий подинтервал кодирования нулевого символа и пропорционально уменьшается текущий подинтервал кодирования единичного символа, а при получении от отправителя единичного символа очередной части информационной последовательности увеличивается текущий подинтервал кодирования единичного символа и пропорционально уменьшается текущий подинтервал кодирования нулевого символа. Далее из текущего подинтервала кодирования нулевого символа в формирователе текущего разрешенного нулевого подинтервала 4 выделяют текущий разрешенный подинтервал кодирования нулевого символа и из текущего подинтервала кодирования единичного символа в формирователе текущего разрешенного единичного подинтервала 5 выделяют текущий разрешенный подинтервал кодирования единичного символа в зависимости от m≥1 ранее кодированных символов информационной символов. На основе данных текущих разрешенных подинтервалов очередные двоичные символы очередной части информационной последовательности арифметически кодируют в арифметическом кодере 6 в очередную часть кодированной последовательности, которую передают по каналу передачи 7 на приемную сторону.
На приемной стороне в Z блоках декодирования 8 принимают очередные биты принятой последовательности. Схема блока декодирования 8 показана на фиг. 2. В каждом блоке декодирования 8 формирователь альтернативной принятой последовательности (АПП) с нулевым продолжением 8.1 и формирователь АПП с единичным продолжением 8.10 формируют альтернативные принятые последовательности с соответствующими продолжениями последовательности, которые в арифметическом декодере 8.2 и арифметическом декодере 8.11, соответственно, арифметически декодируют в очередные части соответствующих им альтернативных восстановленных информационных последовательностей.
При декодировании двоичных символов из АПП с нулевым продолжением в формирователе текущего интервала декодирования 8.3 формируют текущий интервал арифметического декодирования, который формирователь текущего нулевого подинтервала декодирования 8.4 разделяет на текущий нулевой подинтервал декодирования нулевого символа, и формирователь текущего единичного подинтервала декодирования 8.5 разделяет на текущий подинтервал декодирования единичного символа. В соответствии с результатами декодирования m≥1 очередных восстановленных информационных символов из текущих подинтервалов выделяют текущий разрешенный подинтервал декодирования нулевого символа и текущий разрешенный единичный подинтервал декодирования единичного символа в формирователе текущего разрешенного нулевого подинтервала декодирования 8.6 и в формирователе текущего разрешенного единичного подинтервала декодирования 8.7, соответственно. В блоке проверки подинтервалов 8.8 проверяют, находится ли текущее значение принятой последовательности в пределах текущего разрешенного подинтервала декодирования нулевого символа или текущего разрешенного подинтервала декодирования единичного символа этой альтернативной принятой последовательности. При положительном результате проверки в арифметическом декодере 8.2 арифметически декодируют очередные части альтернативной принятой последовательности с ее продолжением последовательности в соответствии с текущими разрешенными подинтервалами декодирования в очередные части соответствующей ей альтернативной восстановленной последовательности. При арифметическом декодировании нулевого символа очередной части восстановленной информационной последовательности из АПП с нулевым продолжением далее в формирователе текущего нулевого подинтервала декодирования 8.4 и формирователе текущего единичного подинтервала декодирования 8.5 увеличивают текущий подинтервал декодирования нулевого символа и пропорционально уменьшают текущий подинтервал декодирования единичного символа для данной АПП, а при декодировании единичного символа - увеличивают текущий подинтервал декодирования единичного символа и пропорционально уменьшают текущий подинтервал декодирования нулевого символа для данной АПП.
Аналогичные действия выполняют при декодировании двоичных символов из АПП с единичным продолжением с использованием формирователя АПП с единичным продолжением 8.10, арифметического декодера 8.11, формирователя текущего интервала декодирования 8.12, формирователя текущего нулевого подинтервала декодирования 8.13, формирователя текущего единичного подинтервала декодирования 8.14, формирователя текущего разрешенного нулевого подинтервала декодирования 8.15, формирователя текущего разрешенного единичного подинтервала декодирования 8.16 и блока проверки подинтервалов 8.17.
В блоке вычисления метрики АПП 8.9 для каждой альтернативной принятой последовательности с ее продолжением вычисляют значение ее метрики суммированием метрики самой последовательности и метрики ее продолжения, где значения метрики продолжения последовательности устанавливают в соответствующее значение в зависимости от соотношения между двоичным значением продолжения последовательности и значением очередного бита принятой последовательности. Из блока вычисления метрики АПП 8.9 вычисленные значение метрики каждой альтернативной принятой последовательности с ее продолжением передают в блок выбора альтернативной принятой последовательности АПП 9.
Если при проверке в блоке проверки подинтервалов 8.8, соответственно, в блоке проверки подинтервалов 8.17, текущее значение альтернативной принятой последовательности находится в пределах текущих разрешенных подинтервалов арифметического декодирования соответствующей альтернативной принятой последовательности с ее продолжением последовательности, то в блоке выбора АПП 9 запоминают очередные части альтернативной восстановленной информационной последовательности, соответствующие альтернативной принятой последовательности с ее продолжением, иначе стирают данную альтернативную принятую последовательность с ее продолжением.
В блоке выбора АПП 9 сравнивают между собой значения метрики альтернативных принятых последовательностей с их продолжениями последовательности и выбирают из них не более предельного числа Z альтернативных принятых последовательностей, имеющих наименьшие значения метрики, которые дополняют соответствующими им продолжениями последовательности, для этих альтернативных принятых последовательностей запоминают очередные части соответствующей им альтернативной восстановленной информационной последовательности и значения метрики.
После поступления всех бит принятой последовательности на приемную сторону в блоке выбора АПП 9 сравнивают между собой значения метрики альтернативных принятых последовательностей и выбирают из них единственную альтернативную принятую последовательность с наименьшим значением метрики и передают получателю в качестве восстановленной информационной последовательности соответствующую выбранной альтернативной принятой последовательности альтернативную восстановленную информационную последовательность.
В способе реализуют следующую последовательность действий.
Алгоритм совместного арифметического и помехоустойчивого кодирования на передающей стороне представлен на фигуре 3.
R
Способы предварительной установки на передающей стороне начального интервала арифметического кодирования и на приемной стороне соответствующего ему начального интервала арифметического декодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Начальный интервал арифметического кодирования длиною D>2 начинается от его начального нижнего значения L, включительно и заканчивается его начальным верхним значением Н исключительно. Начальное нижнее значение интервала кодирования устанавливают в минимальное значение интервала кодирования, а начальное верхнее значения интервала кодирования - в максимальное значение этого интервала. Например, при представлении значений интервала кодирования восемью двоичными символами (разрядность представления интервалов N=8 бит), начальное нижнее значение интервала кодирования арифметического кодирования L[0] в момент времени t=0 устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 0000 0000 в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования Н[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или 1111 1111 в двоичном представлении. Пример начального интервала арифметического кодирования длиною D[0]=256 представлен на фиг. 4 при t=0 (первая строка) и на фиг. 5 при t=0.
Также предварительно устанавливают предельное число Z≥2 альтернативных принятых последовательностей и значение метрики альтернативных принятых последовательностей в нулевое значение. Способы предварительной установки предельного числа Z альтернативных принятых последовательностей известны и описаны, например, в книге Д. Прокис "Цифровая связь". - М., Радио и связь, 2000, стр. 328-349. Например, для исправления двукратных ошибок рекомендуется выбирать предельное число Z альтернативных принятых последовательностей из диапазона значений 8…24, для исправления трехкратных ошибок рекомендуется выбирать предельное число Z альтернативных принятых последовательностей из диапазона значений 24…48, с учетом того, что при увеличении выбранного числа Z можно исправить большее число ошибок передачи, но при этом линейно растет сложность устройств реализации исправления ошибок. Например, для рассматриваемого далее примера установим предельное число Z альтернативных принятых последовательностей равным Z=21.
Способы предварительной установки значения метрики альтернативных принятых последовательностей в нулевое значение известны и описаны, например, в книге Б. Скляр "Цифровая связь. Теоретические основы и практическое применение". - М., Издательский дом "Вильяме", 2003, стр. 432-434. Изначально, до начала приема последовательности на приемной стороне альтернативные принятые последовательности имеют нулевую длину.
На передающей стороне от источника информационной последовательности принимают очередную часть информационной последовательности длиной k≥1 бит. Примерный вид первых 17 очередных частей двоичной ИП длиной k=1 бит показан на фиг. 7(a). Например, первая часть ИП имеет вид "0", вторая часть - "0", четвертая часть - "1" и т.д. Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.
0
1
0
1
0
1
Текущий интервал арифметического кодирования длиною D>2 разделяют на текущий подинтервал кодирования нулевого символа D0≥2 и на текущий подинтервал кодирования единичного символа D1≥2. Способы разделения текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Для арифметического кодирования очередного по счету, t-го символа, где t=1, 2,…, длину D текущего интервала арифметического кодирования, где D=Н-L, разделяют на длину D текущего подинтервала кодирования нулевого символа и длину D текущего подинтервала кодирования единичного символа. Для этого подсчитывают текущее число нулевых символов ИП N и текущее число единичных символов ИП N, закодированных к этому моменту времени в арифметическом кодере. Например, в начальный момент при t=0 текущее число нулевых символов ИП N[0] установлено в значение 1 и текущее число единичных символов ИП N[0] установлено в значение 1. Способы установки в начальный момент арифметического кодирования числа нулевых и единичных символов ИП в единичное значение известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 124-130. Например, как показано на фиг. 4 в первой строке при t=0 указано единичное число нулевых символов ИП (графа N0) и единичное число единичных символов ИП (графа N1). В графе N указывается общее число принятых символов с учетом установленных в начальный момент нулевых и единичных символов ИП, равное N=2 при t=0.
0
0
0
0
1
1
1
1
0
1
Вычисляют текущую вероятность кодирования нулевых символов ИП p[t] по правилу: p[t]=N[t]/(N[t]+N[t]) и текущую вероятность кодирования единичных символов ИП p[t] по правилу: p=N[t]/(N[t]+N[t]). Например, как показано на фиг. 4 в первой строке при t=0, указано значение текущей вероятности кодирования нулевых символов ИП (графа р0) и значение текущей вероятности кодирования единичных символов ИП (графа p1), где начальные значения равны 0,5.
0
0
0
1
1
0
0
1
Длину текущего подинтервала кодирования нулевого символа D[t] определяют по формуле вида D[t]=D[t]×p[t], а длину текущего подинтервала кодирования единичного символа D[t] определяют по формуле вида D[t]=D[t]-D[t]. Например, длина начального интервала кодирования D[0] имеет десятичное значение 255, а длина начального подинтервала нулевых символов D[0] имеет десятичное значение 127 или 01111111 в двоичном представлении, а длина начального подинтервала единичных символов D[0] имеет десятичное значение 255-127=128 или 10000000 в двоичном представлении. Подинтервал кодирования единичных символов расположен сверху подинтервала кодирования нулевых символов, как показано, например, на фиг. 5. Верхнюю границу подинтервала кодирования нулевого символа обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования L включительно до значения Q исключительно, а подинтервал единичного символа простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования Н исключительно. Например, начальное значение Q имеет десятичное значение 127, как показано на фиг. 4 во второй строке при t=0.
a
a
a
a
a
a
a
a
a
a
a
a
a
a
а
а
а
а
а
a
а
m
m
Из текущего подинтервала кодирования нулевого символа D0 и текущего подинтервала кодирования единичного символа D1 в зависимости от m≥1 ранее кодированных символов информационной последовательности выделяют текущий разрешенный подинтервал кодирования нулевого символа D0, где 1≤D0<D0, и, соответственно, текущий разрешенный подинтервал кодирования единичного символа D1, где 1≤D1<D1. Длину D0 текущего разрешенного подинтервала кодирования нулевого символа выбирают как D0=⋅D0, а длину D1 текущего разрешенного подинтервала кодирования единичного символа выбирают как D1=⋅D1, где коэффициент обнаружения ошибок  выбирают в пределах 0<<1. В заявленном способе совместного арифметического и помехоустойчивого кодирования и декодирования коэффициент обнаружения ошибок  является эквивалентом скорости помехоустойчивого кода R, определяемой как отношение длины информационных символов к длине кодированных символов R=k/n, где скорость помехоустойчивого кода выбирается в пределах 0<R<1. Чем меньше значение коэффициента обнаружения ошибок , тем большее число ошибок канала передачи возможно исправить в заявляемом способе совместного арифметического и помехоустойчивого кодирования и декодирования. Например, выберем значение коэффициента обнаружения ошибок =0,8 и число ранее кодированных символов информационной последовательности m=1, а также в начальный момент кодирования t=0 установим для отправителя и получателя, что предыдущий кодированный символ информационной последовательности имел нулевое значение. Длину D0 текущего разрешенного подинтервала кодирования нулевого символа выбирают как D0=⋅D0=0,8⋅127=102 (с округлением до ближайшего целого числа), и длину D1 текущего разрешенного подинтервала кодирования единичного символа выбирают как D1=⋅D1=0,8⋅128=102.
a
a
a
в
a
н
в
н
в
а
a
н
a
Выделение текущего разрешенного подинтервала кодирования нулевого символа D0 из текущего подинтервала кодирования нулевого символа D0 и, сответственно, текущего разрешенного подинтервала кодирования единичного символа D1 из текущего подинтервала кодирования единичного символа D1 в зависимости от m≥1 ранее кодированных символов информационной последовательности может быть выполнено различными способами: начиная от нижнего или верхнего значения соответствующего подинтервала кодирования, или в центральной части подинтервала кодирования, в виде сплошного подинтервала или в виде совокупности разрешенных подинтервалов, перемежающихся подинтервалами из неразрешенных областей кодирования. Возможности по обнаружению и исправлению ошибок передачи при этом в заявляемом способе не меняются. Например, при m=1 для удобства реализации при нулевом ранее кодированном символе ИП предлагается выделение текущего разрешенного подинтервала кодирования нулевого символа длиной D0 в виде одного подинтервала, начинающегося от нижнего значения L интервала кодирования до верхнего значения L текущего разрешенного подинтервала кодирования нулевого символа таким образом, что длина текущего разрешенного подинтервала кодирования нулевого символа равна D0, и данный подинтервал начинается от своего нижнего значения L=L включительно и заканчивается своим верхним значением L исключительно. Например, как показано на фиг. 4 во второй строке при t=0 нижнее значение текущего разрешенного подинтервала кодирования нулевого символа равно L=0 (двоичное значение 0000 0000), а верхнее значение этого подинтервала равно L=102 (двоичное значение 0110 0110). На фиг. 6 расположение текущего разрешенного подинтервала кодирования нулевого символа при нулевом ранее кодированном символе ИП показано как D0/0. При нулевом ранее кодированном символе ИП предлагается выделение текущего разрешенного подинтервала кодирования единичного символа длиной D1 в виде одного подинтервала, начинающегося сверху от верхнего значения Н интервала кодирования до нижнего значения Н текущего разрешенного подинтервала кодирования единичного символа таким образом, что длина текущего разрешенного подинтервала кодирования единичного символа равна D1, как показано на фиг. 6.
н
в
Н
В
Таким образом, в данном примере при нулевом ранее кодированном символе ИП при m=1 ранее кодированных символов ИП выделяют текущий разрешенный подинтервал кодирования нулевого символа в пределах от L=0 до L=102 и текущий разрешенный подинтервал кодирования единичного символа в пределах от Н=153 до Н=255, как показано на фиг. 4 во второй строке в строке выделение разрешенного интервала кодирования "Выделен. разреш. инт".
a
a
a
a
a
a
а
a
В общем случае при m>1 сначала выделяют текущий разрешенный подинтервал кодирования нулевого символа D0 и текущий разрешенный подинтервал кодирования единичного символа D1 в зависимости от первого ранее кодированного символа информационной последовательности. Затем из текущего разрешенного подинтервала кодирования нулевого символа вида D0/0 или D0/1 выделяют текущий разрешенный подинтервал кодирования нулевого символа в зависимости от двух ранее кодированных символов ИП вида D0/00(D0/01) или D0/11 (D0/10) как показано на фиг. 6 и так далее до достижения требуемого числа т ранее кодированных символов ИП.
В результате интервал арифметического кодирования в зависимости от ранее кодированных символов ИП разделяют на разрешенный интервал кодирования и на неразрешенный интервал кодирования. Аналогично, в помехоустойчивом кодировании с обнаружением ошибок множество всех кодовых комбинаций разделяют на множество разрешенных кодовых комбинаций, состоящее из неискаженных ошибками передачи кодовых последовательностей, и на множество неразрешенных кодовых комбинаций, состоящее из искаженных ошибками передачи кодовых последовательностей. Если при приеме принятая последовательность принадлежит множеству неразрешенных кодовых комбинаций, то при использовании помехоустойчивого кодирования обнаружена ошибка в принятых данных. В отличие от этого в предлагаемом способе совместного арифметического и помехоустойчивого кодирования и декодирования ошибка в принятой последовательности выявляется, если текущее состояние арифметического декодирования не соответствует разрешенным подинтервалам декодирования с учетом восстановленных символов ИП.
Способы арифметического кодирования очередной части ИП в соответствии с текущими разрешенными подинтервалами кодирования в очередную часть кодированной последовательности (КП) известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном сжатии двоичных символов очередной части ИП в очередную часть КП в соответствии с текущими значениями разрешенного подинтервала кодирования нулевого символа и разрешенного подинтервала кодирования единичного символа. При поступлении на вход арифметического кодирования очередного двоичного символа очередной части ИП, являющегося единичным двоичным символом, текущий интервал арифметического кодирования устанавливают равным текущему разрешенному подинтервалу кодирования единичного символа, а при поступлении на вход арифметического кодирования нулевого двоичного символа, текущий интервал арифметического кодирования устанавливают равным текущему разрешенному подинтервалу кодирования нулевого символа.
H
B
Например, при поступлении на вход кодирования двоичного символа первой части ИП, являющегося нулевым двоичным символом, текущий интервал кодирования устанавливают равным текущему разрешенному подинтервалу кодирования нулевого символа, начинающимся от L[0]=0 и заканчивающимся Z[0]=102, нижнее значение L[1] текущего интервала арифметического кодирования устанавливают в значение 0, а верхнее значение H[1] - в десятичное значение 102, как показано на фиг. 4 и на фиг. 5 при t=1.
При арифметическом кодировании самый левый бит двоичного представления значения L[1] сравнивают с самым левым битом двоичного представления значения Н[1], например, вида 0000 0000 и 0110 0110, соответственно, как показано на фиг. 4 при t=1. При их совпадении значение самого левого бита двоичных представлений значений L[1] и H[1] считывают в качестве очередного бита очередной части кодированной последовательности (Закод. символ, как показано на фиг. 4). Например, при кодировании первой части ИП первым битом первой части КП является совпавший при сравнении нулевой двоичный символ, как показано на фиг. 4, четвертая строка сверху. Считанный бит удаляют из двоичных представлений значений L[1] и H[1], которые уменьшают до длины 7 бит вида 0000 000 и 110 0110, соответственно. Двоичные символы двоичных представлений значений L[1] и H[1] сдвигают справа налево на один разряд и справа к ним дописывают по нулевому двоичному символу. Например, двоичные представления значений L[1] и H[1] приобретают вид 0000 0000 и 1100 1100, соответственно, как показано на фиг. 4, четвертая строка сверху. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L[t] и H[t] в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала арифметического кодирования.
После каждого выполнения нормализации повторно самый левый бит двоичного представления нижнего значения интервала кодирования сравнивают с самым левым битом двоичного представления верхнего значения интервала кодирования. При их совпадении значение самого левого бита этих двоичных представлений считывают в качестве следующего бита очередной части КП, иначе переходят к кодированию следующего символа и так далее, как показано на фиг. 4.
В результате кодирования первой части информационной последовательности вида "0", показанной на фиг. 7(a), сформирована первая часть кодированной последовательности вида "0", показанная на фиг. 7(б), которую передают на приемную сторону.
0
1
0
1
При поступлении следующей части ИП ее кодирование в очередную часть КП выполняют идентично. После выполнения арифметического кодирования каждого очередного символа уточняют число закодированных нулевых символов ИП и число закодированных единичных символов ИП. Так как закодированный символ в указанном примере является нулевым, то число закодированных нулевых символов ИП увеличивают на единичное значение и оно составляет N[1]=2, число закодированных единичных символов информационной последовательности осталось равным N[1]=1, соответственно, суммарное число закодированных нулевых и единичных информационных символов стало равным 3. Пересчитывают текущее значение вероятности кодирования нулевых символов ИП р[1]=2/3 и текущее значение вероятности кодирования единичных символов ИП p[1]=1/3, как показано в третьей строке сверху на фиг. 4.
0
Перед выполнением арифметического кодирования следующего символа заново текущий интервал арифметического кодирования разделяют на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа, из которых выделяют текущий разрешенный подинтервал кодирования нулевого символа и текущий разрешенный подинтервал кодирования единичного символа. Например, перед кодированием второго по счету символа ИП текущий интервал арифметического кодирования находится в пределах от L[1]=0 до Н[1]=204, текущий подинтервал кодирования нулевого символа - в пределах от L[1]=0 до Q[1]=136, а текущий подинтервал кодирования единичного символа - в пределах от Q[1]=136 до H[1]=204, где значение Q[1] определяется по правилу Q[1]=D[1]×p[1]=204×2/3=136.
a
a
н
в
а
Так как в данном примере при m=1 ранее кодированных символов ИП арифметическому кодированию подлежит второй по счету символ ИП, имеющий нулевое значение, то из текущего подинтервала кодирования нулевого символа выделяют текущий разрешенный подинтервал кодирования нулевого символа с учетом предыдущего кодированного нулевого символа. Длину D0[1] текущего разрешенного подинтервала кодирования нулевого символа выбирают как D0[1]=⋅D0[1]=0,8⋅126=109, соответственно этот подинтервал находится в пределах от L[1]=0 до L[1]=109, как показано на фиг. 4 в пятой строке и на фиг. 5 при t=1.
н
в
Выполняют арифметическое кодирование второго и последующих двоичных символов ИП, как показано на фиг. 4. Например, при кодировании четвертого по счету символа ИП, являющегося единичным символом, из текущего подинтервала кодирования единичного символа выделяют текущий разрешенный подинтервал кодирования единичного символа, находящийся в пределах от H[3]=105 до H[3]=126, как показано на фиг. 4 в десятой строке сверху.
Каждый раз при выполнении нормализации считывают двоичные символы в очередную часть кодированной последовательности. Примерный вид арифметического кодирования первых 17 очередных частей ИП вида "0001 0000 0000 0010 0" в соответствующие очередные части КП вида "0", "0", "_", "_", "01111", "0", "_", "0" и так далее показан на фиг. 7(б). Заметим, что при фиксированной длине очередных частей ИП в результате их арифметического кодирования сформированы очередные части КП переменной длины, что, в частности, определяется переменной избыточностью сжимаемых частей ИП. Например, третья, четвертая, седьмая, десятая и т.д. части КП имеют нулевую длину (не содержат передаваемых символов). В целом КП длиною 17 бит имеет вид "0001 1110 0000 0110 1".
Способы передачи на приемную сторону очередной части КП известны и описаны, например, в книге А.Г. Зюко, Д.Д. Кловский, М.В. Назаров, Л.М. Финк "Теория передачи сигналов". - М.: Радио и связь, 1986, стр. 11. Примерный вид первых 17 частей принятой последовательности (Пр. П) показан на фиг. 8(a). Пусть принятая последовательность общей длиной 17 битов при передаче искажена в девятом и десятом битах принятой последовательности и имеет вид "0001 1110 1100 0110 1".
Алгоритм совместного арифметического и помехоустойчивого декодирования на приемной стороне представлен на фиг. 9. На фиг. 10 представлены альтернативные принятые последовательности в виде древовидной структуры, а на фиг. 11 - примерный вид выбираемых не более Z=21 альтернативных принятых последовательностей.
R
R
R
Для инициализации арифметического декодирования необходимо принять первые по счету N двоичных символов Пр.П, где N есть число двоичных символов представления значений интервалов кодирования и, соответственно, интервалов декодирования. Например, при представлении значений интервала кодирования и интервала декодирования восемью двоичными символами (N=8 бит), принимают первые восемь бит Пр.П вида "0001 1110", как показано на фиг. 12 в столбце считывание двоичных символов "Сч." в начальный момент времени t=0. Принятая последовательность "0001 1110" в начальный момент времени имеет текущее значение 30, вычисляемое как десятичное значение данной двоичной последовательности, в которой наиболее значимый бит находится слева (в начале последовательности), а наименее значимый бит находится справа (в конце последовательности).
R
R
Опишем в общем виде совместное арифметическое и помехоустойчивое декодирования Пр.П на приемной стороне. Действия совместного арифметического и помехоустойчивого декодирования Пр.П на приемной стороне выполняют путем параллельного декодирования нескольких альтернативных принятых последовательностей (АПП). Например, в начальный момент времени имеется единственная альтернативная принятая последовательность, совпадающая с первыми восемью битами Пр.П вида "0001 1110". В момент времени считывания первого после начальных N бит очередной бита принятой последовательности, обозначенного моментом времени t=1, для начальной принятой последовательности, состоящей из первых по счету N двоичных символов принятой последовательности, формируют продолжение АПП в виде нулевого символа и продолжение последовательности в виде единичного символа, как показано на фиг. 10. При считывании следующего бита принятой последовательности (момент времени t=2) для каждой из имеющихся двух АПП формируют продолжения в виде нулевого символа и продолжение в виде единичного символа, в результате на момент времени t=2 число АПП становится 4, на момент времени t=3 число АПП достигает 8 и т.д. Представление альтернативных принятых последовательностей в виде описанной древовидной структуры показано на фиг. 10. Такая структура АПП потенциально позволяет исправлять многократные ошибки передачи в принятой последовательности, причем место ошибок в Пр.П может быть произвольным. Для каждой АПП выполняют описанные далее действия совместного арифметического и помехоустойчивого декодирования.
Например, при предварительно установленном предельном числе Z=21 АПП примерный вид выбираемых не более Z альтернативных принятых последовательностей показан на фиг. 11. Видно, что в этой структуре, называемой усеченным деревом альтернативных принятых последовательностей, число продолжаемых АПП в каждый момент t не превышает заданного значения Z. Например, для начальной альтернативной принятой последовательности вида "0001 1110" формируют 2 продолжения: АПП с продолжением последовательности в виде нулевого символа "0001 1010 0", и АПП с продолжением последовательности в виде единичного символа "0001 1010 1". Для АПП с продолжением последовательности в виде нулевого символа "0001 1010 0" значение метрики продолжения последовательности в виде нулевого символа относительно очередного единичного, девятого по счету на рис. 11 символа принятой последовательности, устанавливают в единичное значение. Так как метрика начальной альтернативной принятой последовательности предварительно установлена в нулевое значение, то АПП с продолжением последовательности в виде нулевого символа "0001 1110 0" имеет значение метрики М=1, как показано на фиг. 11. Для АПП с продолжением последовательности в виде единичного символа "0001 1110 1" значение метрики продолжения последовательности в виде единичного символа относительно очередного, девятого по счету на фиг. 11 бита принятой последовательности, имеющего единичное значение, устанавливают в нулевое значение. Соответственно, АПП с продолжением последовательности в виде единичного символа "0001 1110 1" имеет значение метрики М=0, как показано на фиг. 11.
Число продолжаемых АПП при декодировании девятого по счету символа принятой последовательности равно 2, это число не превышает предельного числа Z=21 АПП и обе альтернативные принятые последовательности продолжают, образуя при декодировании очередного, десятого по счету на фиг. 11 символа принятой последовательности четыре последовательности со значениями метрики от М=0 до М=2, которые при декодировании очередного, одиннадцатого по счету на фиг. 11 бита, принятой последовательности образуют 8 последовательностей со значениями метрики от М=0 до М=3, которые при декодировании очередного, двенадцатого по счету на фиг. 11 символа принятой последовательности образуют 16 последовательностей со значениями метрики от М=0 до М=4 и т.д. Когда число АПП превышает предельное число Z АПП, то из этих последовательностей выбирают не более Z=21 альтернативных принятых последовательностей с наименьшими значениями метрики. По принципу максимального правдоподобия в теории помехоустойчивого кодирования, как описано в книге Б. Скляр "Цифровая связь. Теоретические основы и практическое применение". - М., Издательский дом "Вильяме", 2003, стр. 422-431, чем больше альтернативная принятая последовательность отличается от принятой последовательности по значению метрики М, тем меньше вероятность того, что именно она позволит исправить ошибки передачи, что дает основание такую последовательность стирать.
В приведенном примере во многих продолжаемых АПП текущее значение альтернативной принятой последовательности оказалось вне пределов текущего разрешенного интервала арифметического декодирования этих АПП, то есть такие последовательности не могли быть сформированы на передающей стороне и, соответственно, они подлежат стиранию и их далее не продолжают, как показано символом "" на фиг. 11. При этом оказалась стертой альтернативная принятая последовательность с ее продолжением вида "0001 1110 1100 0110 1" со значением метрики М=0, которая по этой причине ранее считалась наиболее предпочтительной при выборе среди альтернативных принятых последовательностей.
Детально опишем действия совместного арифметического и помехоустойчивого декодирования на приемной стороне.
Способы разделения текущего интервала арифметического декодирования длиною DD каждой альтернативной принятой последовательности на текущий подинтервал декодирования нулевого символа DD0, где DD0≥2, и на текущий подинтервал декодирования единичного символа DD1, где DD1≥2, идентичны способам разделения текущего интервала арифметического кодирования длиною D на текущий подинтервал кодирования нулевого символа D0 и на текущий подинтервал кодирования единичного символа D1 на передающей стороне.
0
1
0
1
0
1
0
1
Для арифметического декодирования очередного по счету, t-го символа, где t=1, 2,…, длину DD текущего интервала арифметического декодирования, где DD=НН-LL, каждой альтернативной принятой последовательности разделяют на длину DD текущего подинтервала декодирования нулевого символа и длину DD текущего подинтервала декодирования единичного символа данной АПП. Текущий интервал арифметического декодирования каждой АПП простирается от ее нижнего значения интервала декодирования LL до верхнего значения интервала декодирования НН. Например, в начальном состоянии при t=0 LL=0 и НН=255, как показано на фиг. 12 в первой строке. Для определения значений DD и DD подсчитывают текущее число нулевых символов восстановленной ИП каждой АПП NN и текущее число единичных символов восстановленной ИП каждой АПП NN, декодированных к этому моменту времени в арифметическом декодере. Например, в начальный момент при t=0 текущее число нулевых символов восстановленной ИП NN[0] установлено в значение 1 и текущее число единичных символов восстановленной ИП NN[0] установлено в значение 1. Например, как показано на фиг. 12 в первой строке при t=0 указано единичное число нулевых символов восстановленной ИП (графа NN0) и единичное число единичных символов восстановленной ИП (графа NN1). В графе NN указывается общее число декодированных символов с учетом установленных в начальный момент нулевых и единичных символов восстановленной ИП, равное NN=2 при t=0.
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]). Например, как показано на фиг. 12 в первой строке при t=0, указано значение текущей вероятности декодирования нулевых символов восстановленной ИП (графа рр0) и значение текущей вероятности декодирования единичных символов восстановленной ИП (графа pp1), где начальные значения равны 0,5.
0
0
0
1
1
0
0
1
Длину текущего подинтервала декодирования нулевого символа DD[t] каждой АПП определяют по формуле вида DD[t]=DD[t]×pp[t], а длину текущего подинтервала декодирования единичного символа DD[t] каждой АПП определяют по формуле вида DD[t]=DD[t]-DD[t]. Например, длина начального интервала декодирования DD[0] АПП имеет десятичное значение 255, длина начального подинтервала декодирования нулевых символов DD[0] АПП имеет десятичное значение 127 или 01111111 в двоичном представлении, а длина начального подинтервала декодирования единичных символов DD[0] АПП имеет десятичное значение 255-127=128 или 10000000 в двоичном представлении. Подинтервал декодирования единичных символов АПП расположен сверху подинтервала декодирования нулевых символов АПП, как показано, например, на фиг. 12. Верхнюю границу подинтервала декодирования нулевого символа АПП обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы интервала декодирования арифметического декодирования LL включительно до значения QQ исключительно, а подинтервал единичного символа простирается от значения QQ включительно до верхней границы интервала декодирования арифметического кодирования НН исключительно. Начальное значение QQ имеет десятичное значение 127, как показано на фиг. 12 во второй строке при t=0.
a
a
a
a
a
a
a
a
a
a
a
a
m
m
Способы выделения в зависимости от m символов восстановленной информационной последовательности каждой альтернативной принятой последовательности из текущего подинтервала декодирования нулевого символа DD0 и из текущего подинтервала декодирования единичного символа DD1 текущего разрешенного подинтервала декодирования нулевого символа DD0, где 1≤DD0<DD0, и, соответственно, текущего разрешенного подинтервала декодирования единичного символа DD1, где 1≤DD1<DD1, идентичны ранее описанным способам выделения из текущего подинтервала кодирования нулевого символа D0 и из текущего подинтервала кодирования единичного символа D1 текущего разрешенного подинтервала кодирования нулевого символа D0 и, соответственно, текущего разрешенного подинтервала кодирования единичного символа D1. Длину DD0 текущего разрешенного подинтервала декодирования нулевого символа выбирают как DD0=⋅DD0, а длину DD1 текущего разрешенного подинтервала декодирования единичного символа выбирают как DD1=⋅DD1.
а
a
a
a
a
a
a
a
B
a
H
B
H
B
Н
В
Например, при выбранных значении коэффициента обнаружения ошибок =0,8 и числе m=1, длину DD0 текущего разрешенного подинтервала декодирования нулевого символа АПП выбирают как DD0=⋅DD0=0,8⋅127=102, и длину DD1 текущего разрешенного подинтервала декодирования единичного символа АПП выбирают как DD1=⋅DD1=0,8⋅128=102. Например, установлено для отправителя и получателя в начальный момент кодирования/декодирования t=0, что предыдущий кодированный/декодированный символ информационной последовательности имеет нулевое значение. Например, для удобства реализации, при нулевом ранее декодированном символе восстановленной ИП в каждой АПП предлагается выделение текущего разрешенного подинтервала декодирования нулевого символа АПП длиной DD0 в виде одного подинтервала, начинающегося от нижнего значения LL интервала декодирования АПП до верхнего значения LL текущего разрешенного подинтервала декодирования нулевого символа АПП таким образом, что длина текущего разрешенного подинтервала декодирования нулевого символа АПП равна DD0, и данный подинтервал начинается от своего нижнего значения LL=LL включительно и заканчивается своим верхним значением LL исключительно. Например, как показано на фиг. 12 во второй строке при t=0 нижнее значение текущего разрешенного подинтервала декодирования нулевого символа АПП равно LL=0 (двоичное значение 0000 0000), а верхнее значение этого подинтервала равно LL=102 (двоичное значение 0110 0110). Соответственно, текущий разрешенный подинтервала декодирования единичного символа АПП находится в пределах от нижнего значения НН=153 до верхнего значения этого подинтервала НН=255, как показано на фиг. 12 во второй строке.
H
B
Н
В
Если текущее значение альтернативной принятой последовательности не находится в пределах текущего разрешенного подинтервала декодирования нулевого символа АПП или текущего разрешенного подинтервала декодирования единичного символа этой АПП, то стирают данную альтернативную принятую последовательность. Например, при представлении значений интервала кодирования восемью двоичными символами текущее значение альтернативной принятой последовательности определяется по последним восьми битам этой АПП. Например, принятая двоичная последовательность вида "0001 1110" АПП вида "0001 1110" имеет десятичное значение 30, показанное на фиг. 12 в графе "Пр. Посл". Текущий разрешенный подинтервал декодирования нулевого символа АПП вида "0001 1110" простирается от LL=0 до LL=102, а текущий разрешенный подинтервала декодирования единичного символа АПП простирается от НН=153 до НН=255. Так как текущее значение альтернативной принятой последовательности находится в пределах одного из текущих разрешенных подинтервалов декодирования АПП, в данном случае в пределах текущего разрешенного подинтервала декодирования нулевого символа АПП, то данная АПП сохраняется и далее подлежит декодированию.
Способы арифметического декодирования каждой АПП в очередные части соответствующей ей альтернативной восстановленной информационной последовательности (АВП) известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43. Они заключаются в последовательном декодировании каждой АПП в соответствии с текущими разрешенными значениями подинтервала декодирования нулевого символа и подинтервала декодирования единичного символа этой АПП.
0
1
0
H
H
B
Примерный вид арифметического декодирования начальной АПП вида "0001 1110" в символы очередной части соответствующей ей АВП показан на фиг. 12. Для декодирования первого символа очередной части АВП текущее значение альтернативной принятой последовательности, равное 30, сравнивают с границами текущего разрешенного подинтервала декодирования нулевого символа АПП DD[0], находящимися, например, в пределах от 0 до 102, и с границами текущего разрешенного подинтервала декодирования единичного символа АПП DD[0], находящимися, например, в пределах от 153 до 255, как показано на фиг. 12 во второй строке при t=0. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение альтернативной принятой последовательности, принимают решение о значении текущего декодированного символа (Дек. симв.) альтернативной восстановленной информационной последовательности, указываемого в правой графе фиг. 12. Так как в данном примере текущее значение альтернативной принятой последовательности оказалось в пределах разрешенного подинтервала декодирования нулевого символа, то декодированный символ является нулевым и следующие границы текущего интервала декодирования устанавливают соответствующими границам разрешенного подинтервала декодирования нулевого символа данной АПП длиною DD[0]. В результате декодирования первого символа устанавливают нижнее значение интервала декодирования арифметического декодирования LL[1] равным значению LL[0], например, LL=0, а верхнее значение интервала декодирования арифметического декодирования HH[1] - равным значению LL=102, как показано на фиг. 12 в третьей строке при t=1.
0
0
0
1
1
0
1
После декодирования каждого символа пересчитывают текущее значение вероятности нулевого символа АВП и текущее значение вероятности единичного символа этой же последовательности, например, после декодирования первого символа, являющегося нулевым, по формуле вида рр[1]=NN[1]/(NN[1]+NN[1])=2/3 и по формуле вида рр[1]=NN[1]/(NN[1]+NN[1])=1/3, соответственно, как показано на фиг. 11 в третьей строке при t=1.
Для каждой АПП формируют продолжение последовательности в виде нулевого символа и продолжение в виде единичного символа. Например, из начальной АПП вида "0001 1110" формируют АПП с продолжением в виде нулевого символа вида "0001 1110 0", и АПП с продолжением в виде единичного символа вида "0001 1110 1", как показано на фиг. 11. Верхнее по рисунку ребро графического представления каждой АПП обозначено как продолжение последовательности в виде нулевого символа "0", а нижнее ребро - как продолжение последовательности в виде единичного символа "1".
После формирования продолжения последовательности вычисляют значение метрики продолжения в виде нулевого символа и значение метрики продолжения в виде единичного символа относительно очередного бита принятой последовательности, при этом значение метрики продолжения в виде нулевого символа относительно очередного бита принятой последовательности вычисляют как нулевое значение, если очередной бит очередной части принятой последовательности является нулевым битом, иначе вычисляют как единичное значение, а также значение метрики продолжения в виде единичного символа относительно очередного бита принятой последовательности вычисляют как нулевое значение, если очередной бит принятой последовательности является единичным битом, иначе вычисляют как единичное значение. Например, как показано на фиг. 11, очередной бит Пр.П, следующий после считывания восьми битов начального пути декодирования, имеет единичное значение. Поэтому относительно этого бита метрика продолжения последовательности в виде нулевого символа имеет единичное значение, а метрика продолжения последовательности в виде единичного символа имеет нулевое значение.
Затем для каждой АПП с ее продолжением последовательности вычисляют значение его метрики, для чего суммируют значения метрики данной последовательности и метрики ее продолжения последовательности. Например, с учетом того, что метрика начальной АПП вида "0001 1110" имеет нулевое значение, метрика АПП вида "0001 1110 0" с продолжением в виде нулевого символа получает единичное значение (М=1), а метрика АПП "0001 1110 1" с продолжением в виде единичного символа получает нулевое значение (М=1), как показано на фиг. 11.
После каждого изменения состояния арифметического декодирования самый левый бит двоичного представления значения LL интервала декодирования АПП сравнивают с самым левым битом двоичного представления значения НН этой АПП, например, для АПП вида "0001 1110 0" при t=1 сравнивают значение LL вида "0000 0000" и значение НН вида "0110 0110", соответственно. При их совпадении выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL и НН удаляют и символы двоичных представлений значений LL и НН сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Например, при этом переменная LL сохранила десятичное значение 0, а НН - получила десятичное значение 204 и двоичное представление "1100 1100", как показано на фиг. 12 в строке "нормализация". Одновременно с этим, самый левый бит текущего значения альтернативной принятой последовательности удаляют и двоичные символы этой последовательности сдвигают справа налево на один разряд и справа к ним дописывают следующий считанный двоичный символ альтернативной принятой последовательности, то есть символ продолжения этой АПП. Например, для АПП вида "0001 1010 0" с продолжением в виде нулевого символа следующим считанным двоичным символом является девятый по счету символ альтернативной принятой последовательности, имеющий нулевое значение, как показано на фиг. 12 в столбце "Сч.". С учетом считанного двоичного символа, текущее значение данной АПП получило десятичное значение 52 и двоичное представление "0011 0100", как показано на фиг. 12 в строке "нормализация".
Для АПП вида "0001 1010 1" с продолжением в виде единичного символа, как показано на фиг. 13, следующим считанным двоичным символом является девятый по счету символ этой альтернативной принятой последовательности, имеющий единчное значение, как показано на фиг. 13 в столбце "Сч.". С учетом считанного двоичного символа, текущее значение данной АПП получило десятичное значение 53 и двоичное представление "0011 0101", как показано на фиг. 13 в строке "нормализация".
Для всех АПП повторно самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения НН, и если они снова совпадают, то повторно выполняют нормализацию идентичным образом и т.д.
Для всех АПП снова определяют длины текущих подинтервалов декодирования, и выделяю их текущие разрешенные подинтервалы декодирования. Например, для АПП видов "0001 1110 0" и "0001 1110 1" текущие разрешенные подинтервалы декодирования нулевого символа и текущие разрешенные подинтервалы декодирования единичного символа на момент декодирования второго информационного символа совпадают. Для АПП вида "0001 1110 0" ее текущее значение 60 находится в пределах текущего разрешенного подинтервала декодирования нулевого символа (от 0 до 109), равно как и для АПП вида "0001 1110 1" ее текущее значение 61 находится в пределах ее текущего разрешенного подинтервала декодирования нулевого символа (от 0 до 109), и для обоих АПП очередным декодированным информационным символом является нулевой символ, как показано на фиг. 12 и фиг. 13.
В результате арифметического декодирования АПП вида "0001 1110 0", показанной на фиг. 8(б), декодируют, например, символы двух первых частей соответствующей ей АВП, имеющей вид "0 0", как показано на фиг. 8(в), аналогично, из АПП вида "0001 1110 1", показанной на фиг. 8(г) декодируют, например, символы двух первых частей соответствующей ей АВП, имеющей вид "0 0", как показано на фиг. 8(д).
Сравнивают между собой значения метрики альтернативных принятых последовательностей с их продолжениями последовательности и выбирают из них не более предельного числа Z альтернативных принятых последовательностей, имеющих наименьшие значения метрики, которые дополняют соответствующими им продолжениями последовательности. Данные способы известны и описаны, например, в книге М. Сибуя, Т. Ямамото "Алгоритмы обработки данных". - М., Мир, 1986, стр. 122-134, и заключаются в поочередном сравнении между собой значений метрики АПП с их продолжениями, сортировке последовательностей по мере возрастания значений метрики и выборе среди отсортированных последовательностей первых Z последовательностей с наименьшими значениями метрики.
Например, на момент приема девятого по счету символа принятой последовательности имеются только две АПП: АПП с продолжением последовательности в виде нулевого символа вида "0001 1110 0" и АПП с продолжением последовательности в виде единичного символа вида "0001 1110 1" со значениями метрики М=1 и М=0, соответственно. Так как число этих АПП не превышает предельного числа Z=21 альтернативных принятых последовательностей, имеющих наименьшие значения метрики, то обе последовательности выбирают и сохраняют.
Для выбранных АПП запоминают очередные части альтернативной восстановленной информационной последовательности, соответствующие этой альтернативной принятой последовательности, и значения метрики. Например, на момент приема девятого по счету символа принятой последовательности для АПП вида "0001 1110 0" и АПП вида "0001 1110 1" запоминают первые две очередные части соответствующих им альтернативных восстановленных информационных последовательностей вида "0 0" и значения метрики М=1 и М=0, соответственно.
При получении следующего бита принятой последовательности каждая из двух сохраненных АПП получает по два продолжения последовательности и т.д. При обработке тринадцатого по счету на фиг. 11 символа принятой последовательности образуют 32 АПП со значениями метрики от М=0 до М=4, из которых выбирают Z=21 лучших по метрике АПП, и т.д. Стирание при этом худших по метрике АПП показано символом "X" на фиг. 11.
0
1
Начиная с некоторого момента времени, число продолжаемых альтернативных принятых последовательностей уменьшается также потому, что во многих АПП их текущее значение оказалось вне пределов текущих разрешенных подинтервалов декодирования этих АПП, то есть такие последовательности не могли быть сформированы на передающей стороне и, соответственно, они подлежат стиранию и их далее не продолжают, как показано символом "" на фиг. 11. Например, при обработке семнадцатого по счету на фиг. 11 символа принятой последовательности оказалась стертой альтернативная принятая последовательность с ее продолжением вида "0001 1110 1100 0110 1" со значением метрики М=0, которая по этой причине ранее считалась наиболее предпочтительной при выборе среди альтернативных принятых последовательностей. Действия декодирования для этой альтернативной принятой последовательности, идентичной принятой последовательности, показаны на фиг. 14. В результате декодирования символов данной последовательности, показанной на фиг. 8(e), получена АВП вида "0 0 0 1 0 0 1 0", показанная на фиг. 8(ж). Например, после декодирования восьмого по счету символа очередной части АВП при выделении разрешенных подинтервалов, показанных на фиг. 14 (продолжение) в предпоследней строке, текущее значение данной альтернативной принятой последовательности, равное 141, сравнивают с границами текущего значения подинтервала декодирования нулевого символа АПП DD, находящимися в пределах от 96 до 132, и с границами текущего значения подинтервала декодирования единичного символа АПП DD, находящимися в пределах от 142 до 143. Так как текущее значение альтернативной принятой последовательности не находится в пределах разрешенных подинтервалов декодирования, то стирают данную альтернативную принятую последовательность.
Аналогичным образом стирают ряд АПП и число продолжаемых АПП уменьшается до 17, а затем до 8, как показано на фиг. 11.
Декодирование АПП вида "0001 1110 0000 01110 1" со значением метрики М=2 показано на фиг. 15. При арифметическом декодировании семнадцати символов данной АПП, показанных на фиг. 8(з), декодированы первые девять частей альтернативной восстановленной информационной последовательности вида "0 0 0 1 0 0 0 0 1", показанной на фиг. 8(и). Как показано на фиг. 11, данная АПП имеет метрику М=2 и является одной из восьми АПП, сохранившихся из всех АПП при приеме первых семнадцати бит принятой последовательности. Однако остальные АПП имеют значения метрики М=3 и более. В ходе дальнейшего декодирования наименьшей по значению метрики будет обладать альтернативная принятая последовательность, продолжающая выявленную АПП с метрикой М[17]=2, так как остальные АПП при любых их возможных продолжениях не могут обеспечить значение метрики меньше М=3.
После прекращения поступления очередных битов принятой последовательности сравнивают между собой значения метрики альтернативных принятых последовательностей и выбирают из них последовательность с наименьшим значением метрики. В приведенном примере будет выбрано продолжение АПП вида "0001 1110 0000 01110 1" со значением метрики на семнадцатом принятом бите М[17]=2, для которой выполняется исправление двух ошибок передачи на первых семнадцати битах принятой последовательности.
Далее передают получателю в качестве восстановленной информационной последовательности соответствующую выбранной альтернативной принятой последовательности альтернативную восстановленную информационную последовательность. Выбранному в примере продолжению АПП вида "0001 1110 0000 01110 1" соответствуют первые девять частей альтернативной восстановленной информационной последовательности вида "0 0 0 1 0 0 0 0 1", показанные на фиг. 8(и).
В данном примере совместное арифметическое и помехоустойчивое кодирование и декодирование обеспечивает исправление двух ошибок передачи в принятой последовательности.
Проверка теоретических предпосылок заявленного способа совместного арифметического и помехоустойчивого кодирования и декодирования выполнялась путем его аналитических исследований.
а
Было выполнено совместное арифметическое и помехоустойчивое кодирование и декодирование очередных частей длиной k=1 бит избыточной информационной последовательности общей длиной 1024 бит с использованием способа-прототипа, для которого выбирались значения скорости помехоустойчивого кода R=1/2 и R=2/3. Также было выполнено совместное арифметическое и помехоустойчивое кодирование и декодирование очередных частей длиной k=1 бит этой же избыточной информационной последовательности общей длиной 1024 бит с использованием предлагаемого способа при выборе значения коэффициента обнаружения ошибок  равным скорости помехоустойчивого кода R=1/2 и R=2/3. Выявлено, что при передаче кодированных последовательностей по каналу связи с ошибками во всех случаях обеспечивается исправление большего числа ошибок передачи с использованием предлагаемого способа по сравнению со способом-прототипом. При этом, при увеличении предельного числа Z альтернативных принятых последовательностей до 24…32, кроме однократных и двухкратных ошибок, обеспечивается исправление трехкратных и части четырехкратных ошибок передачи.
Проведенные исследования подтверждают, что при использовании предлагаемого способа совместного арифметического и помехоустойчивого кодирования и декодирования обеспечивается повышение помехоустойчивости передачи очередных частей кодированной последовательности при воздействии многократных ошибок передачи.