СПОСОБ СОВМЕСТНОГО АРИФМЕТИЧЕСКОГО И ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ (ВАРИАНТЫ) Российский патент 2017 года по МПК H04M13/00 H03M13/00 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация заявленных способов (варианты) представлена на примере системы совместного арифметического и помехоустойчивого кодирования, показанной на фиг. 1. На передающей стороне выполняют совместное арифметическое и помехоустойчивое кодирование очередных частей информационной последовательности, а на приемной стороне - совместное арифметическое и помехоустойчивое декодирование принятой последовательности с обнаружением и исправлением ошибок канала передачи. На передающей стороне при получении от отправителя двоичного символа очередной части информационной последовательности при получении нулевого символа счетчик числа нулевых символов 1 увеличивает число нулевых символов кодирования на единичное значение, а при получении единичного символа счетчик числа единичных символов 2 увеличивает число единичных символов кодирования на единичное значение. Пропорционально подсчитанным числам нулевых и единичных символов кодирования в формирователе границ подинтервалов 3 текущий интервал арифметического кодирования разделяют на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа. В блоке выбора проверочных символов 4 выбирают проверочные символы, которые вместе с символами очередной части информационной последовательности кодируют в арифметическом кодере 5 в очередную часть кодированной последовательности и передают по каналу передачи на приемную сторону.

На приемной стороне в последовательном декодере 7 принимают и запоминают очередные части принятой последовательности, которые в арифметическом декодере 8 декодируют в очередные части декодированной последовательности. При декодировании нулевого символа счетчик числа нулевых символов 9 увеличивает число нулевых символов декодирования на единичное значение, а при декодировании единичного символа счетчик числа единичных символов 10 увеличивает число единичных символов декодирования на единичное значение. Пропорционально подсчитанным числам нулевых и единичных символов декодирования в формирователе границ подинтервалов 11 текущий интервал арифметического декодирования разделяют на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа, в соответствии с которыми в арифметическом декодере 8 выполняют декодирование принятой последовательности. В блоке проверки проверочных символов 12 выполняют поиск ошибок в декодированных проверочных символах и при отсутствии ошибок передают получателю очередную часть восстановленной информационной последовательности, иначе поочередно инвертируют один или несколько битов в запомненных в последовательном декодере 7 очередных частях принятой последовательности и выполняют их арифметическое декодирование до достижения вывода об отсутствии ошибок передачи.

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

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

Способы предварительной установки на передающей стороне начального интервала арифметического кодирования и на приемной стороне соответствующего ему начального интервала арифметического декодирования известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 35-43. Начальный интервал арифметического кодирования начинается от его начального нижнего значения и заканчивается его начальным верхним значением. Начальное нижнее значение интервала кодирования устанавливают в минимальное значение, а начальное верхнее значения интервала кодирования - в максимальное значение. Например, при представлении значений интервала кодирования восемью двоичными символами, начальное нижнее значение интервала кодирования арифметического кодирования L[0] в момент времени t=0 устанавливают в минимальное значение, равное нулевому значению в десятичном представлении или 00000000 в двоичном представлении, где старшие двоичные символы записывают слева, а начальное верхнее значение интервала кодирования арифметического кодирования Н[0] устанавливают в максимальное значение, равное 255 в десятичном представлении или 11111111 в двоичном представлении. Пример начального интервала арифметического кодирования представлен на фиг. 3 при t=0 (первая строка) и на фиг. 4 при t=0.

На передающей стороне от источника информации принимают очередную часть информационной последовательности длиной k≥1 бит. Примерный вид первых шести очередных частей двоичной ИП длиной k=2 бита показан на фиг. 5(a). Например, первая часть ИП имеет вид "11", вторая часть - "10", третья часть - "01". Единичные значения битов на фигурах показаны в виде заштрихованных импульсов, нулевые значения битов - в виде незаштрихованных импульсов.

Способы разделения текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа известны и описаны, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". – М.: ДИАЛОГ-МИФИ, 2002, стр. 35-43. Длину начального интервала арифметического кодирования I[0], равную I[0]=Н[0]-L[0], разделяют на начальные значения подинтервала нулевого символа D₀[0] и подинтервала единичного символа D₁[0], длины которых прямо пропорциональны начальным значениям вероятностей кодируемых нулевых символов р₀[0] и единичных символов p₁[0], соответственно. Длину начального подинтервала единичных символов D₁[0] определяют по формуле вида D₁[0]=I[0]×р₁[0], а длину начального подинтервала нулевых символов D₀[0] определяют по формуле вида D₀[0]=I[0]-D₁[0].

Начальное значение вероятности кодируемых нулевых символов р₀[0] вычисляют по формуле вида , а начальное значение вероятности кодируемых единичных символов р₁[0] вычисляют по формуле вида , где N₀[0] - начальное число закодированных нулевых символов, N₁[0] - начальное число закодированных единичных символов, а N[0] - начальное число закодированных нулевых и единичных символов, равное N[0]=N₀[0]+N₁[0]. В известных способах, описанных, например, в книге Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин "Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео". - М.: ДИАЛОГ-МИФИ, 2002, стр. 124-130, устанавливают начальное число закодированных нулевых символов равным N₀[0]=1, а начальное число закодированных единичных символов - равным N₁[0]=1, то есть начальные значения вероятности кодируемых единичных и нулевых символов устанавливают равными: р₁[0]=р₀[0].

Например, длина начального подинтервала единичных символов D₁[0] имеет десятичное значение 128 или 10000000 в двоичном представлении, а длина начального подинтервала нулевых символов D₀[0] имеет десятичное значение 127 или 01111111 в двоичном представлении. Подинтервал единичных символов расположен сверху подинтервала нулевых символов, как показано, например, на фиг. 4. Верхнюю границу подинтервала нулевого символа обозначают как значение Q, и данный подинтервал начинается снизу от нижней границы интервала кодирования арифметического кодирования включительно до значения Q исключительно, а подинтервал единичного символа простирается от значения Q включительно до верхней границы интервала кодирования арифметического кодирования исключительно. Начальное значение Q имеет десятичное значение 127, как показано на фиг. 3 в первой строке при t=0.

После выполнения кодирования каждого очередного символа уточняют число закодированных нулевых символов и единичных символов. После кодирования t символов текущее значение вероятности кодируемых нулевых символов p₀[t] вычисляют по формуле вида , текущее значение вероятности кодируемых единичных символов p₁[t] вычисляют по формуле вида , где N₀[t] - текущее число закодированных нулевых символов, N₁[t] - текущее число закодированных единичных символов, a N[t] - текущее число закодированных нулевых и единичных символов, равное N[t]=N₀[t]+N₁[t]. Соответственно, длину текущего подинтервала единичного символа D₁[t] определяют по формуле вида D₁[t]=I[t]×p₁[t], а длину текущего подинтервала нулевого символа D₀[t] определяют по формуле вида D₀[t]=I[t]-D₁[t].

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

Определяют середину начального интервала арифметического кодирования. Для этого начальное значение интервала кодирования арифметического кодирования I[0], равное I[0]=Н[0]-L[0], разделяют пополам. Например, при представлении значений интервала кодирования восемью двоичными символами, с учетом округления до ближайшего целого числа середина начального интервала арифметического кодирования соответствует значению S=127 в десятичном представлении или 01111111 в двоичном представлении. Пример местоположения середины начального интервала арифметического кодирования относительно текущих подинтервалов кодирования нулевого символа, обозначенных D0, и текущих подинтервалов кодирования единичного символа, обозначенных D1, представлен на фиг. 4.

Для каждой очередной части информационной последовательности длиной k≥1 бит выбирают соответствующие им проверочные двоичные символы фиксированной длиной r≥1 бит.Место проверочных символов выбирают фиксированным относительно расположения очередной части информационной последовательности. Например, после очередной части информационной последовательности, состоящей из двух бит, показанной на фиг. 5(a), выбирают один двоичный проверочный символ. Соответственно, каждый третий символ входных данных в моменты времени t=3, t=6, t=9, и так далее, является выбираемым проверочным символом, априори неизвестным, что подчеркнуто на фиг. 4 знаком "?".

Для выбора каждого из проверочных символов выделяют среди текущего подинтервала кодирования нулевого символа и текущего подинтервала кодирования единичного символа текущий подинтервал, включающий середину начального интервала арифметического кодирования. Например, после арифметического кодирования первой части информационной последовательности, состоящей из двух бит вида "11", текущий подинтервала кодирования нулевого символа D0 имеет границы от 82 до 125, а текущий подинтервала кодирования единичного символа D1 имеет границы от 125 до 254, как показано на фиг. 4 при t=3. Середину начального интервала арифметического кодирования, соответствующую значению S=127, из этих двух подинтервалов включает текущий подинтервала кодирования единичного символа D1. Поэтому проверочным символом в данном случае устанавливают единичный символ. Если бы середину начального интервала арифметического кодирования включал текущий подинтервал кодирования нулевого символа D0, то проверочным символом был бы установлен нулевой символ.

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

Примерный вид выбранного первого проверочного символа (1-й провер. символ) вида "1" для первой части информационной последовательности вида "11" показан на фиг. 5(б).

Формирование очередной части помехоустойчивой последовательности из очередной части информационной последовательности и выбранных проверочных символов может быть выполнено, например, как считывание в очередную часть помехоустойчивой последовательности сначала очередной части информационной последовательности, а вслед за ней считывание выбранных проверочных символов. Способы считывания проверочных символов вместе с очередной частью информационной последовательности в очередную часть помехоустойчивой последовательности известны и описаны, например, в книге В. Шило "Популярные цифровые микросхемы". - М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Для этого очередная часть двоичной информационной последовательности с первого по k-й бит параллельно записывают в первые по счету ячейки памяти регистр сдвига длиной k+r бит. Проверочные символы в виде двоичной последовательности длиной r бит параллельно записывают в последующие, начиная с k+1-й, ячейки памяти этого же регистра сдвига. В результате в регистре сдвига записана очередная часть помехоустойчивой последовательности длиной k+r бит. Например, первая часть помехоустойчивой последовательности (ПП) имеет вид "111", вторая часть - "101", третья часть - "011", как показано на фиг. 5(в).

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

При поступлении на вход арифметического кодирования очередного двоичного символа очередной части помехоустойчивой последовательности, являющегося единичным двоичным символом, текущий интервал кодирования этого символа устанавливают равным предыдущему подинтервалу кодирования единичного символа, а при поступлении на вход арифметического кодирования нулевого двоичного символа, текущий интервал кодирования этого символа устанавливают равным предыдущему подинтервалу нулевого символа. Например, при поступлении на вход арифметического кодирования первого двоичного символа первой части помехоустойчивой последовательности, являющегося единичным двоичным символом, нижнее значение интервала кодирования первого символа L[1] устанавливают равным значению Q, равному, например, 127, а верхнее значение интервала кодирования первого символа арифметического кодирования Н[1] устанавливают равным начальному верхнему значению интервала кодирования арифметического кодирования H[0], равному, например, 255, как показано на фиг. 3 и на фиг. 4 при t=1.

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

После выполнения арифметического кодирования каждого очередного символа уточняют число закодированных нулевых символов и единичных символов. Так как первый закодированный символ является единичным, то число закодированных единичных символов увеличивают на единичное значение и оно составляет N₁[1]=2, и число закодированных нулевых и единичных символов становится равным N[1]=N₀[1]+N₁[1]=3. Пересчитывают текущее значение вероятности кодируемых нулевых символов и текущее значение вероятности кодируемых единичных . В соответствии с этим длина подинтервала нулевого символа D₀[1] становится в 2 раза меньше длины подинтервала единичного символа D₁[1], а параметр Q принимает значение 170, как показано на фиг. 3, вторая строка сверху и на фиг. 4 при t=1.

При поступлении на вход арифметического кодирования второго символа, являющегося единичным двоичным символом, нижнее значение интервала кодирования второго символа L[2] устанавливают равным значению Q, равному, например, 170, а верхнее значение интервала кодирования второго символа арифметического кодирования H[2] устанавливают равным верхнему значению интервала кодирования арифметического кодирования H[1], равному, например, 255, как показано на фиг. 3 при t=2.

После выполнения арифметического кодирования каждого очередного символа уточняют число закодированных нулевых символов и единичных символов. Так как второй сжатый символ является единичным, то число закодированных единичных символов увеличивают на единичное значение и оно составляет N₁[2]=3, и число закодированных нулевых и единичных символов становится равным N[2]=N₀[2]+N₁[2]=4. Пересчитывают текущее значение вероятности кодируемых нулевых символов и текущее значение вероятности кодируемых единичных символов . В соответствии с этим длина подинтервала нулевого символа D₀[2] становится в 3 раза меньше длины подинтервала единичного символа D₁[2], как показано на фиг. 3, третья строка сверху и на фиг. 4 при t=2.

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

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

Например, при поступлении на вход арифметического кодирования второго двоичного символа второй части помехоустойчивой последовательности, являющегося нулевым двоичным символом, нижнее значение текущего интервала кодирования L[5] этого символа, являющегося пятым по счету, устанавливают равным нижнему значению предыдущего подинтервала кодирования нулевого символа, равному, например, 44, а верхнее значение текущего интервала кодирования этого символа Н[5] устанавливают равным значению Q, численно равному, например, 79, как показано на фиг. 3 и на фиг. 4 при t=5.

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

Примерный вид арифметического кодирования первых шести очередных частей помехоустойчивой последовательности вида "111", "101", "011", "101", "111" и "001" в соответствующие очередные части кодированной последовательности вида "1", "10", "0111", "010", "1" и "001" показан на фиг. 5(г).

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

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

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

Способы разделения текущего интервала арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа идентичны способам разделения текущего интервала арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа. Соответственно, текущий подинтервал декодирования единичного символа расположен сверху текущего подинтервала декодирования нулевого символа, как показано, например, на фиг. 8 и фиг. 9. Верхнюю границу текущего подинтервала декодирования нулевого символа обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы текущего интервала декодирования до значения QQ исключительно, а текущий подинтервал декодирования единичного символа простирается от значения QQ включительно до верхней границы текущий интервала декодирования исключительно. Аналогичным арифметическому кодированию образом после выполнения декодирования каждого очередного символа уточняют текущее число NN₀[t] декодированных нулевых символов и текущее число NN₁[t] декодированных единичных символов. После декодирования t символов текущее значение вероятности декодируемых нулевых символов pp₀[t] вычисляют по формуле вида , текущее значение вероятности декодируемых единичных символов pp₁[t] вычисляют по формуле вида , где NN[t] - текущее число декодированных нулевых и единичных символов, равное NN[t]=NN₀[t]+NN₁[t]. Соответственно, длину текущего подинтервала декодирования единичного символа DD₁[t] определяют по формуле вида DD₁[t]=II[t]×pp₁[t], a длину текущего подинтервала декодирования нулевого символа DD₀[t] определяют по формуле вида DD₀[t]=II[t]-DD₁[t], где II[t] - длина текущего интервала арифметического декодирования.

Идентично арифметическому кодированию, устанавливают начальное число декодированных нулевых символов равным NN₀[0]=1, а начальное число декодированных единичных символов - равным NN₁[0]=1, то есть начальные значения вероятности декодируемых единичных и нулевых символов устанавливают равными: pp₁[0]=pp₀[0]. Пример начального состояния арифметического декодирования представлен на фиг. 8 при t=0.

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

Подинтервал декодирования единичных символов расположен сверху подинтервала декодирования нулевых символов. Верхнюю границу подинтервала декодирования нулевых символов обозначают как значение QQ, и данный подинтервал начинается снизу от нижней границы интервала декодирования арифметического кодирования до значения QQ исключительно, а подинтервал декодирования единичных символов простирается от значения QQ включительно до верхней границы интервала декодирования арифметического декодирования исключительно. Начальное значение QQ имеет десятичное значение 127, как показано на фиг. 8 в первой строке и на фиг. 9 при t=0.

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

На вход арифметического декодирования поступает часть принятой последовательности длиной R бит, равной разрядности выполняемых операций арифметического кодирования и декодирования. Первоначально на вход арифметического декодирования считывают первые по очереди 8 бит вида "11101110", что соответствует десятичному числу 238. Текущие считываемые биты (сч.) показаны во втором столбце, в третьем столбце этой же фигуры (Вх. данные) показано текущее значение считанной последовательности, а место текущего значения считанной последовательности относительно текущих подинтервалов декодирования показано в виде стрелки на фиг. 9. Текущее значение считанной последовательности сравнивают с границами начального значения подинтервала декодирования нулевых символов DD₀[0], находящимися, например, в пределах от 0 до 127 и с границами начального значения подинтервала декодирования единичных символов D₁[0], находящимися, например, в пределах от 127 до 255. В зависимости от того, в пределах какого подинтервала декодирования символов оказалось текущее значение считанной последовательности, принимают решение о значении текущего символа декодированной последовательности.

Например, так как текущее значение считанной последовательности оказалось больше значения QQ (238>127), то первый декодированный символ является единичным и следующие границы интервала декодирования устанавливают соответствующими границам значения подинтервала декодирования единичных символов DD₀[0]. В результате декодирования первого символа устанавливают нижнее значение интервала декодирования арифметического кодирования LL[1] равным значению QQ, например, LL[1]=127, а верхнее значение интервала декодирования арифметического кодирования НН[1] - равным предыдущему значению НН[0], например, НН[1]=255, как показано на фиг. 8 во второй строке при t=1.

После декодирования каждого символа пересчитывают текущее значение вероятности декодируемых нулевых символов и текущее значение вероятности декодируемых нулевых символов, например, после декодирования первого символа, являющегося единичным, по формуле вида и по формуле вида , соответственно. Устанавливают текущее значение QQ и текущие подинтервал декодирования единичных символов и подинтервал декодирования нулевых символов, как показано на фиг. 8 и на фиг. 9.

После каждого изменения состояния арифметического декодирования самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения НН, например, при t=2 вида "10101001" и "11111111", соответственно. При их совпадении выполняют нормализацию арифметического декодирования: значение самого левого бита двоичных представлений значений LL и НН удаляют и двоичные символы двоичных представлений значений LL и НН сдвигают справа налево на один разряд и справа к ним в младший разряд дописывают по нулевому двоичному символу. Одновременно с этим, значение самого левого бита считанной последовательности удаляют и двоичные символы считанной последовательности сдвигают справа налево на один разряд и справа к ним дописывают следующий считанный двоичный символ принятой последовательности, например, девятый по счету символ принятой последовательности, являющийся единичным символом, как показано на фиг. 8 в четвертой сверху строке "нормализация". С учетом дописанного двоичного символа, считанной последовательность приобретают двоичное представление "11011101" и десятичное значение 221. Переменная LL принимает десятичное значение 82 и двоичное представление "01010010", а НН - десятичное значение 254 и двоичное представление "11111110". Повторно самый левый бит двоичного представления значения LL сравнивают с самым левым битом двоичного представления значения НН, и если они снова совпадают, то выполняют повторную нормализацию идентичным образом и т.д.

В результате арифметического декодирования первых одиннадцати символов принятой с ошибкой последовательности декодируют с первой по пятую часть декодированной последовательности (ДП), имеющие, например, вид "1П","1П", "111", "111" и "101", как показано, например, на фиг. 6(б) и на фиг. 8 и фиг. 9.

Способы выделения из очередной части декодированной последовательности очередной части восстановленной информационной последовательности и декодированных проверочных символов известны и описаны, например, в книге В. Шило "Популярные цифровые микросхемы". - М.: Радио и связь, 1987, 104-123, с использованием регистров сдвига с параллельной и последовательной записью/считыванием двоичных последовательностей. Очередную часть декодированной последовательности последовательно записывают в ячейки памяти регистра сдвига длиной k+r бит. Из первых по счету ячеек памяти этого регистра сдвига параллельно считывают очередную часть восстановленной информационной последовательности длиной k бит. Из последующих, начиная с k+1-й, ячейки памяти этого же регистра сдвига параллельно считывают декодированные проверочные символы длиной r бит. Например, из первой части ДП вида "111" выделяют первую часть восстановленной информационной последовательности (ВИП) вида "11" и декодированный проверочный символ вида "1".

Если текущий подинтервал декодирования каждого из декодированных проверочных символов включает середину начального интервала арифметического кодирования, то делают вывод об отсутствии ошибок передачи. Например, первый декодированный проверочный символ является единичным символом и его текущий подинтервал декодирования является текущим подинтервалом декодирования единичного символа, включающего значения от 125 до 254. Данный подинтервал декодирования включает в себя середину начального интервала арифметического кодирования, соответствующую значению S=127. Поэтому имеющаяся ошибка передачи не обнаружена при проверке первого декодированного проверочного символа. Аналогичным образом имеющаяся ошибка передачи не обнаружена при последующей проверке второго, третьего и четвертого декодированных проверочных символов. При декодировании пятого проверочного символа, соответствующий ему текущий подинтервал декодирования единичного символа, включающий значения от 110 до 119, не включают значение S=127 середины начального интервала арифметического кодирования, что однозначно свидетельствует об обнаружении ошибки передачи. Например, ошибка в третьем символе принятой последовательности обнаружена при декодировании пятнадцатого по счету символа декодированной последовательности.

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

Например, в запомненной принятой последовательности инвертируют первый бит (Ин1.Пр.П) и первые четыре части запомненной принятой последовательности приобретают вид "0110111010", показанный на фиг. 6(в). Порядок арифметического декодирования запомненной принятой последовательности с инвертированным первым битов показан на фиг. 10. В результате арифметического декодирования Ин1.Пр.П декодируют первую часть декодированной последовательности при инвертированном первом бите (ДП1), имеющий, например, вид "011", как показано, например, на фиг. 6(г) и на фиг. 10. При проверке первого декодированного проверочного символа, соответствующий ему текущий подинтервал декодирования единичного символа, включающий значения от 167 до 252, не включает значение S=127 середины начального интервала арифметического кодирования, что однозначно свидетельствует об обнаружении ошибки передачи.

Так как инвертирование первого бита принятой последовательности не привело к исправлению ошибки передачи, то в запомненной принятой последовательности инвертируют второй бит (Ин2.Пр.П) и первые четыре части запомненной принятой последовательности приобретают вид "1010111010", показанный на фиг. 6(д). Порядок арифметического декодирования запомненной принятой последовательности с инвертированным вторым битов показан на фиг. 11. В результате арифметического декодирования Ин2.Пр.П декодируют первую часть декодированной последовательности при инвертированном втором бите (ДП2), имеющую, например, вид "110", как показано, например, на фиг. 6(e) и на фиг. 11. При проверке первого декодированного проверочного символа, соответствующий ему текущий подинтервал декодирования единичного символа, включающий значения от 84 до 127 исключительно, не включает значение S=127 середины начального интервала арифметического кодирования, что однозначно свидетельствует об обнаружении ошибки передачи.

Так как инвертирование второго бита принятой последовательности не привело к исправлению ошибки передачи, то в запомненной принятой последовательности инвертируют третий бит (Ин3.Пр.П) и первые части запомненной принятой последовательности приобретают вид "11001110101001", показанный на фиг. 6(ж). Порядок арифметического декодирования запомненной принятой последовательности с инвертированным третьим битов показан на фиг. 12. В результате арифметического декодирования Ин3.Пр.П декодируют первую, вторую и частично третью части декодированной последовательности при инвертированном третьем бите (ДПЗ), имеющие, например, вид "111", "101", "01..", как показано, например, на фиг. 6(з), фиг. 13 и фиг. 14. При проверке первого и второго декодированных проверочных символов (ДПС), показанных на фиг. 6(и), соответствующие им текущие подинтервалы декодирования единичного символа включают значение S=127 середины начального интервала арифметического кодирования, на основании чего делают вывод об отсутствии ошибок передачи.

При отсутствии ошибок передачи передают получателю очередную часть восстановленной информационной последовательности, например, первую часть восстановленной информационной последовательности вида "11", показанную на фиг. 6(к), получают очередную часть принятой последовательности и т.д.

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

Временные диаграммы совместного арифметического и помехоустойчивого кодирования первых шести очередных частей информационной последовательности вида "11", "10", "01", "10", "11" и "00" при выборе проверочных символов по вероятности символов информационной последовательности показаны на фиг. 14. Таблица состояний совместного арифметического и помехоустойчивого кодирования данных частей информационной последовательности при выборе проверочных символов по вероятности символов информационной последовательности показана на фиг. 15. По сравнению с ранее описанным первым вариантом, раздельно и вместе подсчитывается число кодируемых нулевых и единичных символов информационной последовательности и проверочных символов. Для этого задают значения начального числа закодированных нулевых символов информационной последовательности, например, Ninf₀[0]=1 и начального числа закодированных единичных символов информационной последовательности, например, Ninf₁[0]=1, и как описывалось ранее, вычисляют вероятность кодируемых нулевых символов информационной последовательности pinf₀ и вероятность кодируемых единичных символов информационной последовательности pinf₁. Одновременно задают значения начального числа закодированных нулевых проверочных символов, например, Nproν₀[0]=1 и начального числа закодированных единичных проверочных символов, например, Nproν₁[0]=1, и таким же образом, вычисляют вероятность кодируемых нулевых проверочных символов pproν₁. и вероятность кодируемых единичных проверочных символов pproν₁. Затем вычисляют значения начального числа всех закодированных нулевых символов путем суммирования начального числа закодированных нулевых символов информационной последовательности и начального числа закодированных нулевых проверочных символов, например, Ν_∑0[0]=Ninf₀[0]+Nproν₀[0]=1+1=2 и начального числа всех закодированных единичных символов путем суммирования начального числа закодированных единичных символов информационной последовательности и начального числа закодированных единичных проверочных символов, например, Ν_∑1[0]=Ninf₁[0]+Nproν₁[0]=1+1=2. Ранее описанным образом вычисляют вероятность всех кодируемых нулевых символов p_∑0 и вероятность всех кодируемых единичных символов p_∑1. Полученные значения записывают, например, при кодировании каждого символа последовательно сверху вниз для символов информационной последовательности, для проверочных символов и для всех символов, как показано на фиг. 15. Разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в соответствии с вероятностью всех кодируемых нулевых символов p_∑0 и вероятность всех кодируемых единичных символов р_∑1.

Выбор очередных проверочных символов по вероятности символов информационной последовательности выполняют следующим образом. Пусть в t-й момент времени вычислена вероятность кодируемых нулевых символов информационной последовательности pinf₀[t] и вероятность кодируемых единичных символов информационной последовательности pinf₁[t], а также с момента выбора предыдущего проверочного символа вычислена вероятность кодируемых нулевых проверочных символов pproν₀[t-1] и вероятность кодируемых единичных проверочных символов pproν₁[t-1]. Если очередной проверочный символ будет иметь нулевое значение, то вероятность кодируемых нулевых проверочных символов при нулевом значении очередного проверочного символа примет значение pproν_{0 при 0}[t], а если очередной проверочный символ будет иметь единичное значение, то вероятность кодируемых нулевых проверочных символов при единичном значении очередного проверочного символа примет значение pproν_{0 при 1}[t]. Из двух возможных вариантов значений очередного проверочного символа выбирают то значение, которое обеспечивает значение вероятности кодируемых проверочных символов наиболее близкую к значению вероятности кодируемых символов информационной последовательности. Для этого вычисляют значение разницы pinf₀[t]-pproν_{0 при 0}[t] и значение разницы pinf₀[t]-pproν_{0 при 1}[t] и сравнивают их по абсолютной величине. Если первое значение разницы меньше или равно второму значению разницы, то выбирают очередной проверочный символ с нулевым значением, иначе выбирают очередной проверочный символ с единичным значением. Например, как показано на фиг. 15, в момент времени t=3 после кодирования первых двух информационных символов выбирают первый проверочный символ. На этот момент вероятность кодируемых нулевых символов информационной последовательности составляет pinf₀[3]=1/4 и вероятность кодируемых единичных символов информационной последовательности - pinf₁[3]=3/4, а вероятность кодируемых нулевых проверочных символов pproν₀[2]=1/2 и вероятность кодируемых единичных проверочных символов pproν₁[2]=1/2. Если первый проверочный символ примет нулевое значение, то pproν₀[3]=2/3≈0,67, а если первый проверочный символ примет единичное значение, то pproν₀[3]=1/3≈0,33. Вычисляют значение разницы pinf₀[3]-pproν_{0 при 0}[3]=1/4- 2/3≈-0,42 и значение разницы pinf₀[3]-pproν_{0 при 1}[3]=1/ 4-1/3=-0,08. По абсолютной величине второе значение разницы меньше, поэтому выбирают очередной проверочный символ как единичный символ, при этом текущее значение вероятности проверочных символов будет ближе всего к текущему значению вероятности символов информационной последовательности.

Примерный вид выбранных проверочных символов для первых шести очередных частей помехоустойчивой последовательности показан на фиг. 14(б), а сформированных с их использованием очередных частей помехоустойчивой последовательности - на фиг. 14(в). Примерный вид арифметического кодирования первых шести очередных частей помехоустойчивой последовательности вида "111", "100", "010", "101", "111" и "000" в соответствующие очередные части кодированной последовательности вида "11", "0111", "100", "10" и "1001" показан на фиг. 14(г).

Примерный вид первых шести частей принятой последовательности (Пр. П) показан на фиг. 16(a). Принятая последовательность при передаче искажена во втором бите и имеет вид "10", "_", "0111", "100", "10" и "1001".

Идентично тому, как при кодировании подсчитывают значения числа закодированных символов информационной последовательности и их вероятности, числа закодированных проверочных символов и их вероятности, числа всех закодированных символов и их вероятности, при декодировании подсчитывают значения числа декодированных нулевых и единичных символов информационной последовательности NNinf₀ и NNinf₁, и их вероятности ppinf₀ и ppinf₁, значения числа декодированных нулевых и единичных проверочных символов NNproν₀ и NNproν₁ и их вероятности рр proν₀ и рр proν₁, значения числа всех декодированных нулевых и единичных символов ΝΝ_∑0 и ΝΝ_∑1 и их вероятности pp_∑0 и pp_∑1. Полученные значения записывают, например, при декодировании каждого символа последовательно для символов восстановленной информационной последовательности (сверху), для декодированных проверочных символов и для всех декодированных символов (снизу), как показано на фиг. 17. Разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа в соответствии с вероятностью всех декодируемых нулевых символов p_∑0 и вероятность всех декодируемых единичных символов р_∑1.

Примерный вид арифметического декодирования искаженных во втором бите запомненных очередных частей принятой последовательности вида "100111100101001" в очередные части декодированной последовательности показан на фиг. 17. Вследствие ошибки принятой последовательности после декодирования второго символа текущее значение считанной последовательности, равное 60, оказалось вне текущего интервала арифметического декодирования, простирающегося от 82 до 254, что однозначно свидетельствует об обнаружении ошибки передачи. Например, ошибка во втором символе принятой последовательности обнаружена при декодировании второго по счету символа декодированной последовательности, как показано на фиг. 16(6).

Для исправления ошибки передачи поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности. Например, в запомненной принятой последовательности инвертируют первый бит (Ин1.Пр.П) и первые шесть частей запомненной принятой последовательности приобретают вид "00011110010001", показанный на фиг. 16(в). Порядок декодирования запомненной принятой последовательности с инвертированным первым битом показан на фиг. 18. В результате декодирования Ин1.Пр.П декодируют первые три части последовательности при инвертированном первом бите (ДП1), имеющие, например, вид "000", "010"и "010", как показано, например, на фиг. 16(г) и на фиг. 18.

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

При проверке первого декодированного проверочного символа в момент времени t=3 вычислена вероятность декодируемых нулевых символов информационной последовательности ppinf₀[3]=3/4 и вероятность декодируемых единичных символов информационной последовательности ppinf₁[3]=1/4, а также с момента выбора предыдущего проверочного символа вычислена вероятность декодируемых нулевых проверочных символов рр proν₀[2]=1/2 и вероятность декодируемых единичных проверочных символов p pproν₁[2]=1/2. Первый декодированный проверочный символ имеет нулевое значение, и вероятность декодируемых нулевых проверочных символов приняла значение рр proν₀[3]=2/3, как показано на фиг. 18 при t=3. Вычисляют значение разницы ppinf₁[3]-рр proν₀[3]=3/4-2/3≈0,08 и значение разницы в случае, если бы декодированный проверочный символ принял единичное значение: ppinf₁[3]-рр proν_{0 при 1} [3]=3/4-1/3≈0,42. Очевидно, что текущая вероятность первого декодированного проверочного символа как нулевого символа соответствует определенной арифметическим декодированием текущей вероятности символов восстановленной информационной последовательности, поэтому при проверке первого декодированного проверочного символа ошибок передачи не выявлено.

Ошибок передачи не выявлено и при проверке второго декодированного проверочного символа при t=6,a при проверке третьего декодированного проверочного символа при t=9, вычислена вероятность декодируемых нулевых символов информационной последовательности ppinf₀[9]=5/8 и вероятность декодируемых единичных символов информационной последовательности рр inf₁[9]=3/8, а также с момента выбора предыдущего проверочного символа вычислена вероятность декодируемых нулевых проверочных символов рр proν₀[8]=3/4 и вероятность декодируемых единичных проверочных символов рр proν₁[8]=1/4. Третий декодированный проверочный символ имеет нулевое значение, и вероятность декодируемых нулевых проверочных символов приняла значение рр proν₀[9]=4/5, как показано на фиг. 18 при t=9. Вычисляют значение разницы ppinf₁[9]-рр proν₀ [9]=5/8-4/5=-0,175 и значение разницы в случае, если бы декодированный проверочный символ принял единичное значение: ppinf₁[9]-рр proν_{0 при 1} [9]=5/8-3/5=0,025. Сравнение двух вычисленных значений по абсолютной величине показывает, что текущая вероятность третьего декодированного проверочного символа как нулевого символа не соответствует определенной арифметическим декодированием текущей вероятности символов восстановленной информационной последовательности, поэтому при проверке третьего декодированного проверочного символа выявлены ошибки передачи, то есть инвертирование первого бита принятой последовательности не привело к исправлению ошибок передачи.

Поэтому в запомненной принятой последовательности инвертируют второй по счету бит (Ин2.Пр.П) и первые шесть частей запомненной принятой последовательности приобретают вид "11011110010001", показанный на фиг. 16(д). Порядок декодирования запомненной принятой последовательности с инвертированным вторым битом показан на фиг. 19. В результате декодирования Ин2.Пр.П декодируют полностью первые три части последовательности при инвертированном втором бите (ДП2), имеющие, например, вид "111", "100" и "010", как показано, например, на фиг. 16(e) и на фиг. 19. При проверке декодированных проверочных символов показанных, например, на фиг. 16(ж), выявлено, что их текущая вероятность соответствует определенной арифметическим декодированием текущей вероятности символов восстановленной информационной последовательности, следовательно, ошибки передачи отсутствуют. При отсутствии ошибок передачи передают получателю очередную часть восстановленной информационной последовательности, например, первую часть восстановленной информационной последовательности вида "11", показанную на фиг. 16(з).

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

Временные диаграммы совместного арифметического и помехоустойчивого кодирования первых пяти очередных частей информационной последовательности вида "11", "10", "01", "10", "11" и "00" при выборе проверочных символов по преобладанию символов информационной последовательности показаны на фиг. 20. Таблица состояний совместного арифметического и помехоустойчивого кодирования данных частей информационной последовательности при выборе проверочных символов по преобладанию символов информационной последовательности показана на фиг. 21. По сравнению с ранее описанным первым вариантом, раздельно подсчитывают число кодируемых нулевых и единичных символов информационной последовательности и вместе подсчитывают число кодируемых нулевых и единичных символов информационной последовательности и проверочных символов. Для этого задают значения начального числа закодированных нулевых символов информационной последовательности, например, Ninf₀[0]=1 и начального числа закодированных единичных символов информационной последовательности, например, Ninf₁[0]=1, и как описывалось ранее, вычисляют текущую вероятность кодируемых нулевых символов информационной последовательности pinf₀ и текущую вероятность кодируемых единичных символов информационной последовательности pinf₁.

Также вычисляют текущего значения числа всех закодированных нулевых символов путем суммирования текущего числа закодированных нулевых символов информационной последовательности и текущего числа закодированных нулевых проверочных символов при их выборе, например, Ν_∑0[t]=Ninf₀[t]+Nproν₀[t] и текущего числа всех закодированных единичных символов путем суммирования текущего числа закодированных единичных символов информационной последовательности и текущего числа закодированных единичных проверочных символов при их выборе, например, N_∑1[t]=Ninf₁[t]+Nproν₁[t]. Ранее описанным образом вычисляют текущую вероятность всех кодируемых нулевых символов p_∑0[t] и текущую вероятность всех кодируемых единичных символов p_∑1[t]. Полученные значения записывают, например, при кодировании каждого символа последовательно сверху вниз для символов информационной последовательности и для всех символов, как показано на фиг. 21. Разделяют текущий интервал арифметического кодирования на текущий подинтервал кодирования нулевого символа и на текущий подинтервал кодирования единичного символа в соответствии с текущей вероятностью всех кодируемых нулевых символов p_∑0[t] и текущей вероятностью всех кодируемых единичных символов p_∑1[t].

Выбор очередных проверочных символов по преобладанию символов информационной последовательности выполняют следующим образом. Пусть перед t-ым моментом времени выбора проверочного символа вычислена вероятность кодируемых нулевых символов информационной последовательности pinf₀[t-1] и вероятность кодируемых единичных символов информационной последовательности pinf₁[t-1], а также вычислена вероятность всех кодируемых нулевых символов p_∑0[t-1] и вероятность всех кодируемых единичных символов p_∑1[t-1]. Если выполняется соотношение вида pinf₀[t-1]≥pinf₁[t-1], то преобладают нулевые символ информационной последовательности и очередной проверочный символ выбирают как имеющий нулевое значение, иначе преобладают единичные символ информационной последовательности и очередной проверочный символ выбирают как имеющий единичное значение. Например, как показано на фиг. 21, в момент времени t=3 после кодирования первых двух информационных символов выбирают первый проверочный символ. На этот момент вероятность кодируемых нулевых символов информационной последовательности составляет pinf₀[2]=3/4 и вероятность кодируемых единичных символов информационной последовательности - pinf₁[2]=1/4. В силу преобладания нулевых символов информационной последовательности очередной проверочный символ выбирают как имеющий нулевое значение. Для символов информационной последовательности значения вероятности не меняются: pinf₀[3]=pinf₀[2]=3/4 и pinf₁[3]=pinf₁[2]=1/4, а вероятность всех кодируемых нулевых символов и вероятность всех кодируемых единичных символов получают значения p_∑1[t]=4/5 и p_∑0[t]=1/5, соответственно, и т.д.

Примерный вид выбранных проверочных символов для первых пяти очередных частей помехоустойчивой последовательности показан на фиг. 20(б), а сформированных с их использованием очередных частей помехоустойчивой последовательности - на фиг. 20(b). Примерный вид арифметического кодирования первых пяти очередных частей помехоустойчивой последовательности вида "000", "010", "010", "000" и "100" в соответствующие очередные части кодированной последовательности вида "00", "1", "011", "_" и "100001" показан на фиг. 20(г). Примерный вид первых пяти частей принятой последовательности (Пр. П) показан на фиг. 22(a). Принятая последовательность при передаче искажена во втором бите и имеет вид "01", "1", "011", "_" и "100001". Примерный вид декодирования искаженных во втором бите запомненных очередных частей принятой последовательности вида "011011100001" в очередные части декодированной последовательности показан на фиг. 23.

Идентично тому, как при кодировании подсчитывают значения числа закодированных символов информационной последовательности и их вероятности, числа всех закодированных символов и их вероятности, при декодировании подсчитывают значения числа декодированных нулевых и единичных символов информационной последовательности NN inf₀ и NN inf₁ и их вероятности рр inf₀ и рр inf₁, значения числа всех декодированных нулевых и единичных символов ΝΝ_∑0 и ΝΝ_∑1 и их вероятности pp_∑0 и рр_∑1. Полученные значения записывают, например, при декодировании каждого символа последовательно для символов восстановленной информационной последовательности (сверху) и для всех декодированных символов (снизу), как показано на фиг. 23. Разделяют текущий интервал арифметического декодирования на текущий подинтервал декодирования нулевого символа и на текущий подинтервал декодирования единичного символа в соответствии с вероятностью всех декодируемых нулевых символов p_∑0 и вероятность всех декодируемых единичных символов p_∑1.

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

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

Например, первый декодированный проверочный символ является единичным символом, как показано на фиг. 23 при t=3. Определенная арифметическим декодированием текущая вероятность единичных символов восстановленной информационной последовательности равна ppinf₁[3]=2/4 и равна текущей вероятности нулевых символов этой последовательности равна ppinf₀[3]=2/4. В соответствии с приведенным выше условием первый декодированный проверочный символ должен быть нулевым символом, следовательно, обнаружены ошибки передачи.

Для исправления ошибки передачи поочередно инвертируют один или несколько битов в запомненных очередных частях принятой последовательности. Например, в запомненной принятой последовательности инвертируют первый бит (Ин1.Пр.П) и первые пять частей запомненной принятой последовательности приобретают вид "111011100001", показанный на фиг. 22(в). Порядок декодирования запомненной принятой последовательности с инвертированным первым битом показан на фиг. 24. В результате декодирования Ин1.Пр.П декодируют первые пять частей последовательности при инвертированном первом бите (ДП1), имеющие, например, вид "111", "111", "111", "111" и "100", как показано, например, на фиг. 22(г) и на фиг. 24. Ошибка выявлена в пятом декодированном проверочном символе, являющимся нулевым символом, как показано на фиг. 24 при t=15. Определенная арифметическим декодированием текущая вероятность единичных символов восстановленной информационной последовательности равна ppinf₀[15]=3/13 и меньше текущей вероятности единичных символов этой последовательности, равной ppinf₁[15]=10/15. В соответствии с приведенным выше условием пятый декодированный проверочный символ должен быть единичным символом, следовательно, обнаружены ошибки передачи.

Поэтому в запомненной принятой последовательности инвертируют второй по счету бит (Ин2.Пр.П) и первые пять частей запомненной принятой последовательности приобретают вид "001011100001", показанный на фиг. 22(д). Порядок декодирования запомненной принятой последовательности с инвертированным вторым битом показан на фиг. 25. В результате декодирования Ин2.Пр.П декодируют полностью первые две части последовательности при инвертированном втором бите (ДП2), имеющие, например, вид "000" и "010", как показано, например, на фиг. 22(e) и на фиг. 25. При проверке декодированных проверочных символов показанных, например, на фиг. 22(ж), выявлено, что они соответствуют преобладающим по текущей вероятности символам восстановленной информационной последовательности, следовательно, ошибки передачи отсутствуют. При отсутствии ошибок передачи передают получателю очередную часть восстановленной информационной последовательности, например, первую часть восстановленной информационной последовательности вида "00", показанную на фиг. 22(з).

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

Было выполнено совместное арифметическое и помехоустойчивое кодирования нескольких очередных частей информационной последовательности с использованием способа-прототипа и вариантов предлагаемого способа, результаты показаны на фиг. 26. Выполнялось совместное арифметическое и помехоустойчивое кодирование N=1024 очередных частей информационной последовательности длиной 2 бита, при использовании проверочных символов длиной 1 бит. Кодированию подвергались очередные части двоичной информационной последовательности с вероятностью нулевых символов 0.3, 0.2, 0.1, 0.01, и 0.005, соответственно. Передаваемая по каналу передачи сжатая последовательность случайным образом искажалась одной ошибкой. На приемной стороне подсчитывалась вероятность обнаружения ошибки и средняя задержка обнаружения ошибок, определяемая в числе декодированных символов с момента ошибки канала передачи до момента ее обнаружения. Заявленные варианты способа совместного арифметического и помехоустойчивого кодирования обеспечивают существенное повышение коэффициента сжатия избыточных информационных последовательностей по сравнению со способом-прототипом при всех значениях вероятности нулевого символа. Для сравнения также получены результаты сжатия избыточных информационных последовательностей арифметическим кодированием без помехоустойчивого кодирования. На фиг. 26 показано, что третий вариант способа совместного арифметического и помехоустойчивого кодирования обеспечивает значения коэффициента сжатия, близкие к значениям коэффициента сжатия арифметического кодирования без помехоустойчивого кодирования.

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

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

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

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

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

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