Способ совместного арифметического и помехоустойчивого кодирования

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

 

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

Заявленное изобретение может быть использовано для обеспечения достоверности избыточной двоичной информации, передаваемой по каналам с ошибками.

Известен способ адаптивного помехоустойчивого кодирования по патенту РФ 2375824, МПК Н04L 1/20 (2006.01) от 10.12.2009, заключающийся в том, что на передающей стороне исходную информацию кодируют помехоустойчивым кодом с переменными параметрами, далее помехоустойчивый код передают в канал связи, на приемной стороне помехоустойчивый код декодируют с обнаружением и исправлением ошибок в зависимости от корректирующей способности выбранного кода, по результатам декодирования помехоустойчивого кода оценивают качество канала связи и выбирают переменные параметры помехоустойчивого кода, обеспечивающие заданную вероятность правильного приема помехоустойчивого кода, и далее эти параметры помехоустойчивого кода сообщают на передающую сторону, отличающийся тем, что на приемной стороне по результатам декодирования помехоустойчивого кода рассчитывают начальную величину избыточности помехоустойчивого кода, обеспечивающую заданную вероятность правильного приема помехоустойчивого кода, оценивают вероятность правильного приема помехоустойчивого кода с выбранными параметрами, вычисляют величину отклонения полученной вероятности правильного приема помехоустойчивого кода от заданной вероятности правильного приема кода и в зависимости от величины этого отклонения корректируют величину избыточности помехоустойчивого кода, которую передают на передающую сторону, где формируют помехоустойчивый код с полученной избыточностью.

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

Известен также способ совместного сжатия и помехоустойчивого кодирования речевых сигналов, описанный, например, в книге С.Н. Кириллов, В.Т. Дмитриев, Д.Е. Крысяев, С.С. Попов "Исследование качества передаваемой речевой информации при различном сочетании алгоритмов кодирования источника и канала связи в условиях воздействия помех". - Рязань, Вестник РГРТУ, Выпуск 23, 2008. Данный способ заключается в том, что предварительно формируют множество способов сжатия речевого сигнала, таких как импульсно-кодовая модуляция, адаптивная дельта-модуляция, адаптивная дифференциальная импульсно-кодовая модуляция, и множество способов помехоустойчивого кодирования, таких как кодирование Хэмминга, кодирование Боуз-Чоудхури-Хоквингема, на передающей стороне от отправителя получают очередную часть речевого сигнала длиною речевая фраза, которую преобразуют в сжатую двоичную затем выполняют помехоустойчивое кодирование сжатой двоичной последовательности с помощью одного из способов помехоустойчивого кодирования, передают на приемную сторону по каналу прямой связи очередную часть кодированной последовательности вместе с информацией об использованном способе сжатия речевого сигнала и способе помехоустойчивого кодирования, на приемной стороне получают очередную часть принятой последовательности, которую последовательно декодируют с использованием соответствующих способа помехоустойчивого декодирования и способа восстановления речевого сигнала, вычисляют оценку качества восстановленного речевого сигнала и полученную оценку сравнивают с пороговым значением качества, если вычисленная оценка качества восстановленного речевого сигнала не хуже порогового значения качества, то передают получателю очередную часть восстановленной информационной последовательности и от отправителя получают очередную часть речевого сигнала и выполняют последующие действия, иначе передают по каналу обратной связи требование изменить способ сжатия речевого сигнала и способ помехоустойчивого кодирования, и выполняют последующие действия.

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

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

Наиболее близким по своей технической сущности к заявленному способу совместного арифметического и помехоустойчивого кодирования является способ совместного арифметического и помехоустойчивого кодирования по патенту США 6892343, МПК Н03M 13/00 (2006.01) от 10.05.2005. Способ - прототип совместного арифметического и помехоустойчивого кодирования заключается в том, что на передающей стороне от отправителя получают очередной символ информационной последовательности, из предварительно сформированного множества выбирают проверочные символы, которые записывают вместе с очередными символами информационной последовательности, разделяют текущий интервал арифметического кодирования на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа, выполняют арифметическое кодирование очередных символов из числа символов информационной последовательности и проверочных символов в очередную часть сжатой последовательности, преобразуют очередную часть сжатой последовательности в очередную часть модулированной последовательности, передают очередную часть модулированной последовательности на приемную сторону, выполняют на передающей стороне перечисленные действия до тех пор, пока поступают очередные символы информационной последовательности, на приемной стороне получают очередную часть принятой последовательности, которую запоминают, разделяют текущий интервал арифметического декодирования на подинтервал декодирования нулевого символа и на подинтервал декодирования единичного символа, запомненные очередные части принятой последовательности арифметически декодируют, из декодированных символов выделяют очередные символы восстановленной информационной последовательности и декодированные проверочные символы, если декодированные проверочные символы принадлежат предварительно сформированному множеству проверочных символов, то делают вывод об отсутствии ошибок передачи и передают получателю очередной символ восстановленной информационной последовательности, иначе поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности и выполняют их арифметическое декодирование до достижения вывода об отсутствии ошибок передачи, выполняют перечисленные действия на приемной стороне до тех пор, пока поступают очередные части принятой последовательности.

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

Общая схема способа-прототипа совместного арифметического и помехоустойчивого кодирования представлена на фиг. 1. На передающей стороне выполняют совместное арифметическое и помехоустойчивое кодирование очередных символов информационной последовательности (ИП), а на приемной стороне - совместное декодирование с обнаружением и исправлением ошибок канала передачи. На передающей стороне при получении от отправителя от одного до нескольких символов информационной последовательности в блоке проверочных символов 1 из предварительно сформированного множества проверочных символов выбирают проверочные символы (ПС), которые последовательно записывают вместе с очередными символами информационной последовательности и кодируют в арифметическом кодере 2 в очередную часть сжатой последовательности (СП). Текущее состояние арифметического кодера определяется текущими значениями счетчика числа нулевых кодируемых символов 3 и счетчика числа единичных кодируемых символов 4, в соответствии с которыми в формирователе границ подинтервалов кодирования 5 разделяют текущий интервал арифметического кодирования на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа. Затем в модуляторе 6 преобразуют очередную часть сжатой последовательности в очередную часть модулированной последовательности, которую передают по каналу передачи 7. На приемной стороне получают очередную часть принятой последовательности и в демодуляторе - последовательном декодере 8 демодулируют ее в двоичную последовательность, которую запоминают. Запомненные очередные части принятой последовательности декодируют в арифметическом декодере 9. Текущее состояние арифметического декодера определяется текущими значениями счетчика числа нулевых декодируемых символов 10 и счетчика числа единичных декодируемых символов 11, в соответствии с которыми в формирователе границ подинтервалов декодирования 12 разделяют текущий интервал арифметического декодирования на подинтервал декодирования нулевого символа и на подинтервал декодирования единичного символа. Из очередной части декодированной последовательности выделяют очередную часть восстановленной информационной последовательности и декодированные проверочные символы. Декодированные проверочные символы из очередных частей декодированной последовательности в блоке сравнения 13 сравнивают со считанными из блока проверочных символов 14 соответствующими проверочными символами, и при нахождении случая совпадения делают вывод об отсутствии ошибок передачи и передают получателю очередную часть восстановленной информационной последовательности. Иначе в демодуляторе - последовательном декодере 8 поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности, которые арифметически декодируют и выполняют последующие действия до достижения вывода об отсутствии ошибок передачи.

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

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

Таким образом, недостатком ближайшего аналога (прототипа) является сравнительно большая трудоемкость исправления ошибок передачи.

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

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

В предлагаемой совокупности действий на передающей стороне выполняют арифметическое кодирование очередных символов информационной последовательности с учетом предыдущего кодированного символа в очередную часть сжатой последовательности. Возможный порядок кодирования показан на решетчатой диаграмме допустимых путей совместного арифметического и помехоустойчивого кодирования двоичной информационной последовательности, представленной на рис. 2. Данная решетчатая диаграмма представляет собой ориентированный граф, который в начальный момент времени t0 начинается с одного из двух начальных состояний, обозначенных как начальное состояние предыдущего символа "0" или начальное состояние предыдущего символа "1". Если первый кодируемый символ ИП является нулевым, то при установленном начальном состоянии "0" кодирование в момент времени t1 переходит в состояние "кодирование нулевого символа после нулевого символа" или кратко состояние "0/0". Если первый кодируемый символ ИП является единичным, то при установленном начальном состоянии "0" кодирование в момент времени t1 переходит в состояние "кодирование единичного символа после нулевого символа" или кратко состояние "1/0". При установленном начальном состоянии "1" кодирование в момент времени t1 при единичном первом кодируемом символе ИП переходит в состояние "кодирование единичного символа после единичного символа" или кратко "1/1" и при нулевом первом кодируемом символе ИП кодирование переходит в состояние "кодирование нулевого символа после единичного символа" или кратко "0/1". Аналогичным образом, начиная с момента времени t2 и до тех пор, пока поступают очередные символы информационной последовательности, из текущего состояния кодирования переходит в последующее состояние с учетом предыдущего кодированного символа. Таким образом, решетчатая диаграмма допустимых путей кодирования, показанная на рис. 2, состоит из четырех состояний кодирования, обозначенных вершинами "0/0", "1/0", "0/1" и "1/1", из каждого текущего состояния при кодировании очередного нулевого или единичного символа ИП возможен переход в одно из двух соответствующих последующих состояний, а в каждое последующее состояние возможен переход из двух соответствующих предыдущих состояний. Например, из состояния "0/0" при кодировании очередного нулевого символа ИП кодирование переходит в состояние "0/0", а при кодировании очередного единичного символа ИП кодирование переходит в состояние "1/0" и т.д. Соответственно, в очередное состояние "0/0" можно перейти из предыдущего состояния "0/0" при предыдущем нулевом кодированном символе, или из предыдущего состояния "1/0" при предыдущем единичном кодированном символе и т.д. Из каждого текущего состояния кодирования можно перейти в 2 соответствующих последующих состояний из общего числа четырех состояний, и в каждое текущее состояние кодирования можно перейти из 2 соответствующих предыдущих состояний из общего числа четырех состояний, что составляет множество допустимых путей кодирования. В сжатой последовательности, сформированной в соответствии с данной решетчатой диаграммой допустимых путей кодирования, имеется помехоустойчивая избыточность, позволяющая обнаружить факт искажения сжатой последовательности из-за ошибок передачи. Если при декодировании принятой последовательности обнаруживают, что хотя бы один переход из предыдущего состояния в последующее состояние не принадлежит множеству допустимых путей кодирования, то это однозначно свидетельствует о наличии ошибки передачи.

В предлагаемом способе обнаружение ошибок выполняют при декодировании каждого очередного символа восстановленной ИП, а не после нескольких очередных символов восстановленной ИП с соответствующими им проверочными символами, как выполняют в способе-прототипе, что позволяет выполнять декодирование меньшего числа Μ двоичных символов принятой последовательности от момента возникновения ошибки канала передачи до ее обнаружения.

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

Заявленный способ поясняется чертежами, на которых показаны:

- на фиг. 1 - общая схема совместного арифметического и помехоустойчивого кодирования в ближайшем аналоге (прототипе);

- на фиг. 2 - решетчатая диаграмма допустимых путей совместного арифметического и помехоустойчивого кодирования двоичной информационной последовательности;

- на фиг. 3 - общая схема совместного арифметического и помехоустойчивого кодирования в предлагаемом способе;

- на фиг. 4 - алгоритм совместного арифметического и помехоустойчивого кодирования на передающей стороне;

- на фиг. 5 - временные диаграммы совместного арифметического и помехоустойчивого кодирования на передающей стороне;

- на фиг. 6 - таблица состояний совместного арифметического и помехоустойчивого кодирования информационной последовательности;

- на фиг. 7 - последовательность состояний совместного арифметического и помехоустойчивого кодирования информационной последовательности;

- на фиг. 8 - временные диаграммы совместного арифметического декодирования и исправления ошибок на приемной стороне;

- на фиг. 9 - алгоритм совместного арифметического декодирования и исправления ошибок на приемной стороне;

- на фиг. 10 - таблица состояний совместного декодирования с ошибкой передачи в третьем бите;

- на фиг. 11 - таблица состояний совместного декодирования принятой последовательности с ошибкой передачи при инвертировании ее первого бита;

- на фиг. 12 - таблица состояний совместного декодирования принятой последовательности с ошибкой передачи при инвертировании ее второго бита;

- на фиг. 13 - таблица состояний совместного декодирования принятой последовательности с ошибкой передачи при инвертировании ее третьего бита;

- на фиг. 14 - сравнение трудоемкости исправления ошибок передачи для способа-прототипа и заявленного способа.

Реализация заявленного способа представлена на примере системы совместного арифметического и помехоустойчивого кодирования, показанной на фиг. 3. На передающей стороне выполняют совместное арифметическое и помехоустойчивое кодирование очередных символов информационной последовательности, а на приемной стороне - совместное декодирование с обнаружением и исправлением ошибок канала передачи. На передающей стороне полученный от отправителя очередной символ информационной последовательности кодируют в арифметическом кодере 2. Текущее состояние арифметического кодера определяется текущими значениями счетчика числа нулевых кодируемых символов 3 и счетчика числа единичных кодируемых символов 4, в соответствии с которыми в формирователе границ подинтервалов кодирования 5 сначала разделяют текущий интервал арифметического кодирования на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа, а затем указанные подинтервалы разделяют на подинтервал кодирования нулевого символа после нулевого символа, на подинтервал кодирования нулевого символа после единичного символа, на подинтервал кодирования единичного символа после нулевого символа, и на подинтервал кодирования единичного символа после единичного символа, соответственно. Поэтому в арифметическом кодере 2 очередной символ информационной последовательности кодируют с учетом предыдущего кодированного символа в очередную часть сжатой последовательности, которую передают по каналу передачи 7. На приемной стороне получают очередную часть принятой последовательности и в последовательном декодере 15 ее запоминают. Запомненные очередные части принятой последовательности декодируют в арифметическом декодере 9 с учетом предыдущего декодированного символа. Текущее состояние арифметического декодера определяется текущими значениями счетчика числа нулевых декодируемых символов 10 и счетчика числа единичных декодируемых символов 11, в соответствии с которыми в формирователе границ подинтервалов декодирования 12 сначала разделяют текущий интервал арифметического декодирования на подинтервал декодирования нулевого символа и на подинтервал декодирования единичного символа, а затем указанные подинтервалы разделяют на подинтервал декодирования нулевого символа после нулевого символа, на подинтервал декодирования нулевого символа после единичного символа, на подинтервал декодирования единичного символа после нулевого символа, и на подинтервал декодирования единичного символа после единичного символа, соответственно.

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

Алгоритм совместного арифметического и помехоустойчивого кодирования на передающей стороне представлен на фигуре 4.

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

На передающей стороне от отправителя получают очередной двоичный символ информационной последовательности. Примерный вид первых восемнадцати символов ИП вида "111111111011111010" показан на фиг. 5(a). Видно, что информационная последовательность является избыточной: вероятность получения единичных символов существенно превышает вероятность получения двоичных символов. Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.

Способы разделения текущего интервала арифметического кодирования на подинтервал кодирования нулевого символа после нулевого символа, на подинтервал кодирования нулевого символа после единичного символа, на подинтервал кодирования единичного символа после нулевого символа, и на подинтервал кодирования единичного символа после единичного символа заключаются в следующем. Сначала разделяют текущий интервал арифметического кодирования на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа, что описано, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М., ДИАЛОГ-МИФИ, 2002, стр. 35-43.

Текущий интервал арифметического кодирования состоит из множества значений от нижнего значения интервала кодирования до верхнего значения интервала кодирования. В начальном состоянии арифметического кодирования начальное нижнее значение интервала кодирования устанавливают в минимальное значение, а начальное верхнее значения интервала кодирования - в максимальное значение. Например, при представлении значений интервала кодирования восемью двоичными символами, начальное нижнее значение интервала кодирования арифметического кодирования L[0] устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 00000000 в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования Н[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или 11111111 в двоичном представлении. Пример начального состояния (Нач. сост.) арифметического кодирования представлен на фиг. 6 при t0 и на фиг. 7. Например, произвольно выбрано единичное начальное состояние предыдущего символа (нач. сост.) "1", как показано в первой строке на фиг. 7 при t0.

Текущий интервал арифметического кодирования разделяют на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в соответствии с текущими значениями вероятности кодируемых нулевых символов p0[i] и вероятности кодируемых единичных символов p1[i]. Текущее значение вероятности кодируемых нулевых символов p0[i] при арифметическом кодировании i-го очередного двоичного символа информационной последовательности вычисляют по формуле вида , а текущее значение вероятности кодируемых единичных символов p1[i] вычисляют по формуле вида , где N0[i] - текущее число закодированных нулевых символов, N1[i] - текущее число закодированных единичных символов, a N[i] - текущее число закодированных нулевых и единичных символов, равное N[i]=Ν0[i]+Ν1[i]. Соответственно, для текущего значения вероятности кодируемых нулевых символов p0[i] и текущего значения вероятности кодируемых нулевых символов p1[i] должно выполняться ограничение вида: p0[i]+p1[i]=1. В известных способах, описанных, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ - МИФИ, 2002, стр. 124-130, в начальном состоянии кодирования устанавливают начальное число закодированных нулевых символов равным N0[0]=1, а начальное число закодированных единичных символов - равным N1[0]=1, то есть начальные значения вероятности кодируемых единичных и нулевых символов устанавливают равными: p1[0]=p0[0]=1/2.

Начальное значение интервала кодирования арифметического кодирования I[0], равное I[0]=H[0]-L[0], разделяют на начальные значения подинтервала нулевых символов D0[0] и подинтервала единичных символов D1[0], длины которых прямо пропорциональны начальным значениям вероятностей кодируемых нулевых символов р0[0] и единичных символов p1[0], соответственно. Начальную длину подинтервала единичных символов D1[0] определяют по формуле вида D1[0]=I[0]×p1[0], а начальную длину подинтервала нулевых символов D0[0] определяют по формуле вида D0[0]=I[0]-D1[0]. Например, начальная длина подинтервала единичных символов D1[0] имеет десятичное значение 128 или 10000000 в двоичном представлении, а начальная длина подинтервала нулевых символов D0[0] имеет десятичное значение 127 или 01111111 в двоичном представлении. Подинтервал единичных символов расположен сверху подинтервала нулевых символов, как показано, например, на фиг. 7. Верхнюю границу подинтервала нулевых символов обозначают как значение , и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения исключительно, а подинтервал единичных символов простирается от значения включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Начальное значение имеет десятичное значение 127, как показано на фиг. 6 в первой строке при t=0.

При кодировании очередного, i-го по счету символа ИП, соответственно, текущий интервал кодирования арифметического кодирования равный I[i]=H[i]-L[i], разделяют на текущие значения подинтервала нулевых символов D0[i] и подинтервала единичных символов D1[i], длины которых прямо пропорциональны текущим значениям вероятностей кодируемых нулевых символов p0[i] и единичных символов p1[i], соответственно.

Затем текущий подинтервал кодирования нулевого символа разделяют на текущий подинтервал кодирования нулевого символа после нулевого символа и на текущий подинтервал кодирования нулевого символа после единичного символа, а текущий подинтервал кодирования единичного символа разделяют на текущий подинтервал кодирования единичного символа после нулевого символа и на текущий подинтервал кодирования единичного символа после единичного символа в соответствии с текущими значениями вероятности кодируемых нулевых символов р0[i] и вероятности кодируемых единичных символов p1[i]. Текущий подинтервал кодирования единичного символа после единичного символа D1/1[i] вычисляют по формуле D1/1[i]=Dl[i]×pl[i], текущий подинтервал кодирования единичного символа после нулевого символа D1/0[i] вычисляют по формуле D1/0[i]=D1[i]-D1/1[i]. Текущий подинтервал кодирования нулевого символа после нулевого символа D0/0[i] вычисляют по формуле D0/0[i]=D0[i]×p0[i], текущий подинтервал кодирования нулевого символа после единичного символа D0/1[i] вычисляют по формуле D0/1[i]=D0[i]-D0/0[i]. Например, начальная длина подинтервала кодирования единичного символа после единичного символа D1/1[0] имеет десятичное значение 64, и начальная длина подинтервала кодирования нулевого символа после нулевого символа D0/0[0] имеет десятичное значение 64. Обозначим верхнюю границу подинтервала кодирования нулевого символа после нулевого символа как значение , равное , а верхнюю границу подинтервала кодирования единичного символа после нулевого символа как значение , равное . В соответствии с этим подинтервал кодирования нулевого символа после нулевого символа D0/0 начинается снизу от нижней границы интервала кодирования арифметического кодирования до значения исключительно, а подинтервал кодирования нулевого символа после единичного символов D0/1 простирается от значения включительно до значения исключительно. Соответственно, подинтервал кодирования единичного символа после нулевого символа D1/0 начинается снизу от значения включительно до значения исключительно, а подинтервал кодирования единичного символа после единичного символа D1/1 простирается от значения включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Пример начальных значений L, , , и H показан на фиг. 6 в первой строке при t=0 и на фиг. 7.

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

Например, первый символ информационной последовательности является единичным символом, а в качестве предыдущего кодированного символа в начальном состоянии установлен единичный символ. Среди имеющихся четырех текущих подинтервалов кодирования, таких как D0/0[0], D0/1[0], D1/0[0] и D1/1[0] выбирают текущий подинтервал кодирования единичного символа после единичного символа D1/1[0] и текущий интервал кодирования первого символа ИП I[1] становится равным I[1]=D1/1[0]. Нижняя граница текущего интервала кодирования первого символа становится равной , соответствующей десятичному числу 191 или 10111111 в двоичном представлении. Верхняя граница текущего интервала кодирования первого символа становится равной H[1]=H[0], соответствующей десятичному числу 255 или 11111111 в двоичном представлении, как показано на фиг. 6 и на фиг. 7 при t=1.

Самый левый бит двоичного представления значения L[l] сравнивают с самым левым битом двоичного представления значения H[1], например, вида 10111111 и 11111111, соответственно. При их несовпадении переходят к сжатию следующего символа.

Иначе при их совпадении значение самого левого бита двоичных представлений значений L и H считывают в качестве очередного бита сжатой последовательности (Закод. символ на фиг. 6). Например, при кодировании первого символа ИП самые левые биты двоичных представлений значений L[1]=10111111 и H[1]=11111111 совпали, как показано на фиг. 6 при t=1, вторая строка сверху. Считанный бит удаляют из двоичных представлений значений L[1] и H[1], которые уменьшаются до длины 7 бит вида 0111111 и 1111111, соответственно. Двоичные символы двоичных представлений значений L[1] и H[1] сдвигают справа налево на один разряд и справа к ним дописывают по нулевому двоичному символу. Например, двоичные представления значений L[1] и H1] приобретают вид 01111110 и 11111110, соответственно. Нижняя граница L[1] становится равной десятичному числу 126, а верхняя граница H1] - 254, как показано на фиг. 6, третья строка сверху. Способы считывания двоичных символов с удалением считанных символов известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Операции сдвига справа налево на один разряд и дописывания справа нулевого двоичного символа увеличивают значения L[1] и H[1] в 2 раза и называются нормализацией параметров арифметического кодирования. Способы сдвига на один разряд в сторону старших разрядов двоичных последовательностей и записи в освободившийся младший разряд нулевого двоичного символа известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей, и по своей сути являются умножением на два десятичных значений нижнего и верхнего значений интервала кодирования.

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

После выполнения кодирования каждого очередного символа уточняют число закодированных нулевых символов и единичных символов. Так как первый кодированный символ является единичным, то число закодированных единичных символов увеличивают на единичное значение и оно составляет N1[1]=2, и число закодированных нулевых и единичных символов становится равным N[1]=N0[1]+N1[1]=3, [1]=3. Пересчитывают текущее значение вероятности кодируемых нулевых символов и текущее значение вероятности кодируемых единичных символов . В соответствии с этим пересчитывают длины текущих подинтервалов. Сначала разделяют текущий интервал арифметического кодирования от 126 до 254 на подинтервал кодирования нулевого символа и на подинтервал кодирования единичного символа. В соответствии с текущим значением вероятности кодируемых символов длина подинтервала кодирования нулевого символа от 126 до 171 стала в 2 раза меньше длины подинтервала кодирования единичного символа от 171 до 254. Текущее значение стало равным 171. Затем текущий подинтервал кодирования нулевого символа D0[1] разделяют на текущий подинтервал кодирования нулевого символа после нулевого символа D0/0[1] и на текущий подинтервал кодирования нулевого символа после единичного символа D0/1[1], а текущий подинтервал кодирования единичного символа D1[1] разделяют на текущий подинтервал кодирования единичного символа после нулевого символа D1/0[1] и на текущий подинтервал кодирования единичного символа после единичного символа D1/1[1] в соответствии с текущими значениями вероятности кодируемых нулевых символов р0[1]=1/3 и вероятности кодируемых единичных символов р1[1]=2/3. Соответственно, параметр принял значение 141, а параметр принял значение 199. При кодировании второго символа ИП, являющегося единичным символом, с учетом предыдущего для него единичного кодированного символа, в качестве следующего интервала кодирования выбирают текущий подинтервал кодирования единичного символа после единичного символа D1/1[1]. Соответственно, нижняя граница текущего интервала кодирования второго символа становится равной , соответствующей десятичному числу 199 или 11000111 в двоичном представлении, а верхняя граница - равной H[2]=H[1], соответствующей десятичному числу 254 или 11111110 в двоичном представлении, как показано на фиг. 6 и на фиг. 7 при t=2 и т.д.

При кодировании десятого символа ИП, являющегося нулевым символом, с учетом предыдущего для него единичного кодированного символа, в качестве следующего интервала кодирования выбирают текущий подинтервал кодирования нулевого символа после единичного символа D0/1[9], лежащий в пределах от 35 до 48, как показано на фиг. 6 при t=9. Соответственно, нижняя граница текущего интервала кодирования десятого символа становится равной , соответствующей десятичному числу 35 или 00100011 в двоичном представлении, а верхняя граница - равной , соответствующей десятичному числу 48 или 00110000 в двоичном представлении, как показано на фиг. 6 и на фиг. 7 при t=10.

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

Примерный вид кодирования первых восемнадцати символов ИП вида "1111111110111110" в очередные части сжатой последовательности (СП) вида "1111110010011001" показан на фиг. 5(б). Например, для удобства практической реализации длину очередной части сжатой последовательности можно установить равной 8 бит (1 байт), соответственно, первая часть СП имеет вид "11111100", вторая часть СП имеет вид "10011001" и т.д.

Способы передачи на приемную сторону очередной части сжатой последовательности известны и описаны, например, в книге А.Г. Зюко, Д.Д. Кловский, М.В. Назаров, Л.М. Финк "Теория передачи сигналов". - М.: Радио и связь, 1986, стр. 11. Примерный вид принятой последовательности (Пр. П) показан на фиг. 8(a). Пусть принятая последовательность при передаче искажена в третьем бите и имеет вид "11011100 10011001".

Алгоритм совместного арифметического декодирования и исправления ошибок на приемной стороне представлен на фиг. 9.

Способы запоминания очередных частей принятой последовательности известны и описаны, например, в книге: В. Шило "Популярные цифровые микросхемы". - М., Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей.

Способы разделения текущего интервала арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа в соответствии с текущими значениями вероятности декодируемых нулевых символов pp0[i] и вероятности декодируемых единичных символов pp1[i] идентичны ранее описанным способам разделения текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в соответствии с текущими значениями вероятности кодируемых нулевых символов p0[i] и вероятности кодируемых единичных символов p1[i].

Для этого в начальном состоянии арифметического декодирования, идентичном начальному состоянию арифметического кодирования, начальное нижнее значение интервала декодирования LL[0] устанавливают в минимальное значение, а начальное верхнее значения интервала декодирования НН[0] - в максимальное значение. Пример начального состояния (Нач. сост.) арифметического декодирования представлен на фиг. 10 при t0. Так же, как на передающей стороне, на приемной стороне установлено единичное начальное состояние предыдущего символа (нач. сост.) "1".

Текущий интервал арифметического декодирования разделяют на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа в соответствии с текущими значениями вероятности декодируемых нулевых символов pp0[i] и вероятности декодируемых единичных символов pp1[i], которые вычисляют по формулам вида и , где NN0[i] - текущее число декодированных нулевых символов, NN1[i] - текущее число декодированных единичных символов, a NN[i] - текущее число декодированных нулевых и единичных символов, равное NN[i]=NN0[i]+NN1[i]. В начальном состоянии декодирования устанавливают NN0[0]=l и NN1[0]=1.

Начальное значение интервала декодирования арифметического декодирования II[0], равное II[0]=НН[0]-LL[0], разделяют на начальные значения подинтервала декодирования нулевых символов DD0[0] и подинтервала декодирования единичных символов DD1[0] по формулам вида DD1[0]=II[0]×ppl[0] и DD0[0]=II[0]-DDl[0]. Верхнюю границу подинтервала декодирования нулевых символов обозначают как значение , и данный подинтервал начинается снизу от нижней границы интервала декодирования арифметического декодирования до значения исключительно, а подинтервал декодирования единичных символов простирается от значения включительно до верхней границы интервала декодирования арифметического декодирования исключительно. Например, начальное значение имеет десятичное значение 127, как показано на фиг. 10 в первой строке при t=0.

Затем текущий подинтервал декодирования нулевого символа разделяют на текущий подинтервал декодирования нулевого символа после нулевого символа и на текущий подинтервал декодирования нулевого символа после единичного символа, а текущий подинтервал декодирования единичного символа разделяют на текущий подинтервал декодирования единичного символа после нулевого символа и на текущий подинтервал декодирования единичного символа после единичного символа в соответствии с текущими значениями вероятности декодируемых нулевых символов pp0[i] и вероятности декодируемых единичных символов pp1[i].

Текущий подинтервал декодирования единичного символа после единичного символа DD1/1[i] вычисляют по формуле DD1/1[i]=DD1[i]×pp1[i], текущий подинтервал декодирования единичного символа после нулевого символа DDl/0[i] вычисляют по формуле DD1/0[i]=DD1[i]-DD1/l[i]. Текущий подинтервал декодирования нулевого символа после нулевого символа DD0/0[i] вычисляют по формуле DD0/0[i]=DD0[i]×pp0[i], текущий подинтервал декодирования нулевого символа после единичного символа DD0/0[i] вычисляют по формуле DD0/1[i]=DD0[i]-DD0/0[i]. Обозначим верхнюю границу подинтервала декодирования нулевого символа после нулевого символа как значение , равное , а верхнюю границу подинтервала декодирования единичного символа после нулевого символа как значение , равное . В соответствии с этим подинтервал декодирования нулевого символа после нулевого символа DD0/0 начинается снизу от нижней границы интервала декодирования арифметического декодирования до значения исключительно, а подинтервал декодирования нулевого символа после единичного символов простирается от значения включительно до значения исключительно. Соответственно, подинтервал декодирования единичного символа после нулевого символа DD1/0 начинается снизу от значения включительно до значения исключительно, а подинтервал декодирования единичного символа после единичного символа DD1/l простирается от значения включительно до верхней границы интервала декодирования арифметического декодирования исключительно. Пример начальных значений LL, , , и НН показан на фиг. 10 в первой строке при t=0. В начальном состоянии декодирования устанавливают начальное значение предыдущего декодированного символа, например, единичное значение.

На вход арифметического декодирования поступает часть принятой последовательности длиной R бит, равной разрядности выполняемых операций, как и при ранее описанном арифметическом кодировании. Например, первоначально на вход арифметического декодирования считывают первые по очереди 8 бит вида "11011100", что соответствует десятичному числу 220.

Запомненные очередные части принятой последовательности арифметически декодируют с учетом предыдущего декодированного символа. Для декодирования первого символа выполняют следующие действия. Текущее значение считанной последовательности сравнивают с границами начального значения подинтервала декодирования нулевых символов DD0[0], находящимися, например, в пределах от 0 до 127 и с границами начального значения подинтервала декодирования единичных символов DD1[0], находящимися, например, в пределах от 127 до 255. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение считанной последовательности, принимают решение о декодировании очередного символа декодированной последовательности.

Например, так как текущее значение считанной последовательности оказалось больше значения , то первый декодированный символ является единичным. Так как установлено начальное единичное значение предыдущего декодированного символа, то следующие границы интервала декодирования устанавливают соответствующими границам подинтервала декодирования единичного символа после единичного символа DD1/1[0]. В результате декодирования первого символа устанавливают нижнее значение интервала декодирования арифметического кодирования LL[1] равным значению , например, LL[1]=191, а верхнее значение интервала декодирования арифметического кодирования HH[1] - равным предыдущему значению HH[0], например, HH[1]=255, как показано на фиг. 10 во второй строке при t=1. После декодирования каждого символа пересчитывают текущее значение вероятности декодируемых нулевых символов и текущее значение вероятности декодируемых нулевых символов, например, после декодирования первого символа, являющегося единичным, по формуле вида и по формуле вида , соответственно.

Декодированный единичный символ считывают с выхода арифметического декодирования в качестве первого символа декодированной последовательности.

После каждого изменения состояния арифметического декодирования самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения HH, например, при t=1 вида "10111111" и "11111111", соответственно. При их совпадении выполняют нормализацию арифметического декодирования, иначе продолжают декодирование.

Например, после декодирования первого символа самый левый бит двоичного представления значения LL[1] совпал с самым левым битом двоичного представления значения HH[1] и поэтому выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL и HH удаляют и двоичные символы двоичных представлений значений LL и HH сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Одновременно с этим, значение самого левого бита входных данных удаляют и двоичные символы входных данных сдвигают справа налево на один разряд и справа к ним дописывают следующий двоичный символ принятой последовательности, например, девятый по счету символ принятой последовательности, являющийся единичным символом, как показано на фиг. 10 в третьей строке "нормализация". С учетом дописанного двоичного символа, входные данные приобретают двоичное представление "10111001" и десятичное значение 185. Переменная LL принимает десятичное значение 126 и двоичное представление "00011000", а НН - десятичное значение 254 и двоичное представление "11111110".

Текущий интервал декодирования в соответствии с текущими значениями вероятности декодируемых нулевых символов рр0[1]=1/3 и вероятности декодируемых единичных символов рр1[1]=2/3 разделяют на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, которые затем в таком же соответствии разделяют на текущий подинтервал декодирования нулевого символа после нулевого символа и на текущий подинтервал декодирования нулевого символа после единичного символа, на текущий подинтервал декодирования единичного символа после нулевого символа и на текущий подинтервал декодирования единичного символа после единичного символа, границы которых показаны на фиг. 10 в третьей строке "нормализация".

Далее выполняют арифметическое декодирование второго символа с учетом предыдущего декодированного символа. Текущее десятичное значение входных данных, равное 185, определяет, что второй декодированный символ должен быть единичным, но значение входных данных находится между значениями и , что соответствует подинтервалу декодирования единичного символа после нулевого символа. Таким образом, выявлено несовпадение предыдущего декодированного символа с соответствующим предыдущим декодированным символом из текущего подинтервала декодирования и тем самым выявлен факт наличия ошибок передачи, одной или нескольких. Применительно к представленному на рис. 2 множеству допустимых путей кодирования, при декодировании первых двух символов обнаружено, что один переход из предыдущего состояния в последующее состояние не принадлежит множеству допустимых путей кодирования, что однозначно свидетельствует о наличии ошибки передачи. Например, на фиг. 8(б) показан пример декодированной последовательности (ДП) вида "11" до момента обнаружения ошибок передачи в принятой последовательности, показанной на фиг. 8(a).

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

Например, в принятой последовательности сначала инвертируют первый бит, как показано на фиг. 8(в). Принятая последовательность с инвертированным первым битом (ИН.1Пр.П) имеет вид "0101110010011001". Попытка арифметического декодирования с учетом предыдущего декодированного символа принятой последовательность с инвертированным первым битом представлена на фиг. 11.

Из принятой последовательности с инвертированным первым битом первоначально на вход арифметического декодирования считывают первые по очереди 8 бит вида "01011100", что соответствует десятичному числу 92. Начальное состояние подинтервалов декодирования показано на фиг. 11 в первой строке при t=0. Значение 92 входных данных лежит в диапазоне значений от =64 до =127, что соответствует подынтервалу декодирования нулевого символа после единичного символа. Следовательно, первый декодированный символ является нулевым символом. При этом начальное единичное значение предыдущего декодированного символа, установленное априори, совпадает с соответствующим предыдущим декодированным символом из текущего подинтервала декодирования и тем самым пока наличие ошибок передачи не выявлено.

В результате декодирования первого символа текущий подинтервал декодирования установлен от 64 до 127, как показано во второй строке на фиг. 11 при t=1. Пересчитывают текущее значение вероятности декодируемых нулевых символов и текущее значение вероятности декодируемых нулевых символов, например, после декодирования первого символа, являющегося нулевым, по формуле вида и по формуле вида , соответственно. Самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения НН, например, при t=1 вида "01000000" и "01111111", соответственно. При выявленном совпадении выполняют нормализацию арифметического декодирования, как показано в третьей строке на фиг. 11. После нормализации значение LL равно 128, а НН=254, входные данные получили вид "10111001" и имеют десятичное значение 185. В соответствии с текущими значениями вероятности декодируемых единичных и нулевых символов интервал декодирования разделяют на текущие подинтервалы декодирования. Далее выполняют арифметическое декодирование второго символа с учетом предыдущего декодированного символа. Текущее десятичное значение входных данных, равное 185, лежит в диапазоне значений <185<, следовательно, второй декодированный символ должен быть нулевым символом, но данный подинтервал декодирования является подинтервалом декодирования нулевого символа после единичного символа. Таким образом, выявлено несовпадение предыдущего декодированного символа с соответствующим предыдущим декодированным символом из текущего подинтервала декодирования, а значит, инвертирование первого бита в принятой последовательности не привело к исправлению ошибок передачи. Например, на фиг. 8(г) показан пример декодированной последовательности (ДП1) вида "00" до момента обнаружения ошибок передачи в принятой последовательности с инвертированным первым битом.

Затем в принятой последовательности инвертируют второй бит, как показано на фиг. 8(д). Принятая последовательность с инвертированным вторым битом (ИН.2Пр.П) имеет вид "1001110010011001". Попытка арифметического декодирования с учетом предыдущего декодированного символа принятой последовательность с инвертированным вторым битом представлена на фиг. 12.

Из принятой последовательности с инвертированным вторым битом первоначально на вход арифметического декодирования считывают первые по очереди 8 бит вида "10011100", что соответствует десятичному числу 156. Начальное состояние подинтервалов декодирования показано на фиг. 12 в первой строке при t=0. Значение 156 входных данных лежит выше значения =127, что соответствует подинтервалу декодирования единичного символа. Следовательно, первый декодированный символ является единичным символом. Однако значение входных данных лежит в диапазоне значений от =127 до =191, что соответствует подинтервалу декодирования единичного символа после нулевого символа. Поэтому уже при декодировании первого символа выявлено наличие ошибок, а значит, инвертирование второго бита в принятой последовательности не привело к исправлению ошибок передачи. Например, на фиг. 8(ж) показан пример декодированной последовательности (ДП2) вида "1" до момента обнаружения ошибок передачи в принятой последовательности с инвертированным вторым битом.

Затем в принятой последовательности инвертируют третий бит, как показано на фиг. 8(з). Принятая последовательность с инвертированным третьим битом (ИН.3Пр.П) имеет вид "111110010011001". Попытка арифметического декодирования с учетом предыдущего декодированного символа принятой последовательности с инвертированным третьим битом представлена на фиг. 13.

Из принятой последовательности с инвертированным третьим битом первоначально на вход арифметического декодирования считывают первые по очереди 8 бит вида "11111100", что соответствует десятичному числу 252. Начальное состояние подинтервалов декодирования показано на фиг. 13 в первой строке при t=0. Например, в результате арифметического декодирования с учетом предыдущего декодированного символа принятой последовательности с инвертированным третьим битом вида "111110010011001" восстановлена информационная последовательность вида "1111111110", составляющая первые 10 битов закодированной на передающей стороне информационной последовательности. Восстановленная информационная последовательность (ВИП) показана на фиг. 8(e). При декодировании каждого символа данной принятой последовательности сравнивались предыдущий декодированный символ с соответствующим предыдущим декодированным символом из текущего подинтервала декодирования, и соответствующие символы совпали при декодировании всех символов, на основании чего сделан вывод об отсутствии ошибок передачи. Все переходы из предыдущего состояния декодирования в последующее состояние декодирования принадлежат множеству допустимых путей декодирования, показанных на фиг. 2.

Таким образом, ошибка передачи в принятой последовательности является исправленной при инвертировании ее третьего бита.

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

Было выполнено совместное арифметическое и помехоустойчивое кодирования нескольких очередных частей информационной последовательности с использованием способа-прототипа и предлагаемого способа, результаты показаны на фиг. 14. В соответствии со способом - прототипом выполнялось совместное арифметическое и помехоустойчивое кодирование очередных частей информационной последовательности длиной k=4 бит общей длиной 1024 бит, при использовании проверочных символов длиной r=1 бит. Арифметическому и помехоустойчивому кодированию подвергались очередные части двоичной информационной последовательности с вероятностью нулевых символов 0.2, 0.1, 0.01 и 0.001, соответственно. Передаваемая по каналу передачи сжатая последовательность искажалась одной ошибкой на позиции сотого по счету бита. На приемной стороне подсчитывалась задержка обнаружения ошибок, определяемая как число декодированных символов от момента ошибки в канале передачи до ее обнаружения. Для каждого значения вероятности нулевых символов двоичная информационная последовательность случайным образом генерировалась 1000 раз и подсчитывалась средняя задержка в битах обнаружения ошибок. Аналогичным образом подсчитывалась средняя задержка обнаружения ошибок в соответствии с предлагаемым способом совместного арифметического и помехоустойчивого кодирования. Средняя задержка обнаружения ошибок с использованием способа-прототипа имеет значения от 9.8 до 15.4 при вероятности нулевых символов от 0.001 до 0.2. Соответственно, средняя задержка обнаружения ошибок с использованием предлагаемого способа имеет значения от 7.8 до 12.2 при вероятности нулевых символов от 0.001 до 0.2. Округляя значения средней задержки обнаружения ошибок до ближайших сверху целых значений, получаем, что для исправления одиночных ошибок с использованием способа-прототипа необходимо выполнить до 10-16 вариантов инвентирования битов в запомненных очередных частях принятой последовательности, а при использовании предлагаемого способа необходимо выполнить до 8-13 вариантов инвентирования этих битов. Для исправления многократных ошибок (кратности до М) с использованием способа-прототипа необходимо выполнить до 1024-65536 вариантов инвентирования битов в запомненных очередных частях принятой последовательности, а при использовании предлагаемого способа необходимо выполнить до 256-8192 вариантов инвентирования этих битов.

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

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

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



 

Похожие патенты:

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

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