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

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

Иллюстрации

Показать все

Реферат

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

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

Известен способ адаптивного помехоустойчивого кодирования по патенту РФ 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], разделяют пополам. Например, при представлении значений интервала кодирования восемью двоичными символами, с учетом округления до ближайшего целого числа сере