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

 

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

Область техники, к которой относится изобретение

Данное изобретение в общем относится к последовательным декодерам Витерби и, в частности, к последовательным декодерам Витерби, используемым в системах радиосвязи многостанционного доступа с кодовым разделением каналов (МДКР).

Уровень техники

Фиг.1 иллюстрирует принципиальную схему передающей системы 10 МДКР, описываемой во Временном нормативе Ассоциации Промышленности Электросвязи TIA/EIA/IS-95-A: "Стандарт совместимости мобильной станции/базовой станции для двухрежимной широкополосной системы сотовой связи с расширенным спектром". Эта передающая система может быть обеспечена, например, в базовой станции передающей системы сотовой связи для передачи сигналов на мобильные телефоны в сотовой ячейке, окружающей базовую станцию.

Входящая линия 11 обеспечивает речевой или информационный сигнал, который может быть цифровым или аналоговым. В приводимом ниже примере исходят из того, что входной сигнал является речевым. Входящей линией может быть аналоговая или цифровая линия коммутируемой телефонной сети общего пользования (КТСОП) или иной источник речевых сигналов. Если входной речевой сигнал является аналоговым, то сигнал дискретизируют и преобразуют в цифровую форму аналого-цифровым преобразователем (не изображен). Источник 12 данных с переменной скоростью передачи принимает оцифрованные выборки речевого сигнала и кодирует этот сигнал с получением пакетов кодированной речи с одинаковой длительностью кадра. Источник 12 данных с переменной скоростью передачи может, например, преобразовывать оцифрованные выборки входного речевого сигнала в оцифрованные речевые параметры, характеризующие входной речевой сигнал, с помощью методики линейного кодирования с предсказанием. В одном из вариантов реализации изобретения источник данных с переменной скоростью передачи является вокодером переменной скорости, описываемым подробно в патенте США №5414796. Источник 12 данных с переменной скоростью передачи обеспечивает пакеты данных переменной скорости передачи при четырех возможных скоростях передачи кадров: 9600, 4800, 2400 и 1200 бит/сек, которые в данном документе называются полной, половинной, одной четвертой и одной восьмой скоростью. Пакеты, кодируемые с полной скоростью, содержат 172 информационных бита; выборки, кодируемые на половинной скорости, содержат 80 информационных бит; выборки, кодируемые на одной четвертой скорости, содержат 40 информационных бит; и выборки, кодируемые на одной восьмой скорости, содержат 16 информационных бит. Все пакеты независимо от размера имеют длительность одного кадра, т.е. 20 мсек. Прочие системы могут применять другие скорости передачи данных или размеры пакетов. В данном документе термины "кадр" и "пакет" могут взаимно заменять друг друга в применении.

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

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

Пакеты переменной скорости передачи, формируемые источником 12 данных, направляют в формирователь 13 пакетов, который выборочно прилагает биты контроля при помощи циклического избыточного кода (КЦИК) и замыкающие (хвостовые) биты. Пакеты переменной скорости передачи от формирователя 13 пакетов затем направляют в кодер 14, который кодирует биты пакетов переменной скорости передачи для обнаружения и исправления ошибок. В одном из вариантов реализации изобретения кодер 14 является сверточным последовательным кодером Витерби с 1/3 скоростью передачи. Сверточно кодированные символы затем направляют в модулятор 16, который формирует модулированный сигнал. Выполнение модулятора МДКР подробно изложено в патентах США №5103459 и 4901307. Модулированный сигнал затем направляют в аналоговый преобразователь 22 для преобразования в аналоговый сигнал, затем направляют в передатчик 24, который преобразует с повышением частоты и усиливает данный сигнал для передачи через антенну 26.

Фиг.2 иллюстрирует соответствующие узлы мобильного телефона 28 или другой мобильной станции, принимающей передаваемый сигнал. Сигнал принимают с помощью антенны 30, преобразуют с понижением частоты и усиливают, если необходимо, приемником 31 и демодулируют демодулятором 32 в поток символов, который остается сверточно кодированным. Затем данный сигнал направляют в последовательный декодер 34 Витерби, который декодирует сверточно кодированный поток символов. Декодер также подразделяет принимаемый сигнал на пакеты и определяет соответствующую скорость передачи кадров для каждого пакета. Скорость передачи кадров можно определить, например, путем обнаружения длительности отдельных бит данного кадра. Аспекты приводимого в качестве примера последовательного декодера Витерби описаны в совместно поданной заявке на патент США №08/126477 от 24 сентября 1993 г.

Для декодирования потока символов декодер 34 применяет блок 36 показателя ошибок в ветвлении, который принимает символы от демодулятора, и блок 38 суммирования /сравнения/ выбора (ССВ), который вырабатывает разряды решения на основе символов. Для повышения рабочих характеристик декодер осуществляет обратную последовательность от того, что он считает показателем оптимального состояния, с помощью блока 40 обратной последовательности, который обрабатывает разряды решения, принимаемые от ССВ 38. В каждом цикле процесса 2^K-1 разрядов решения запоминают блоком обратной последовательности в ЗУПВ 41 обратной последовательности, при этом "К" является ограничением по длине кода, применяемого кодером. Состояние с низшим показателем оптимального состояния пересылают от ССВ в блок обратной последовательности в качестве оптимального состояния.

По завершении L циклов процесса начинается обратная последовательность. Операцией обратной последовательности управляет контроллер 42 обратной последовательности. Процесс обратной последовательности выполняют считыванием из ЗУПВ обратной последовательности разряда решения для оптимального состояния для предыдущего цикла (L-1) процесса. Считанный разряд решения сдвигают в самый младший разряд оптимального состояния. Блок обратной последовательности затем считывает из ЗУПВ обратной последовательности разряд решения, соответствующий новому значению оптимального состояния для цикла L-2 процесса. Этот процесс выполняют всего L раз, в конечном счете считывая разряд решения вычисленного оптимального состояния для цикла 0 процесса. Заключительный разряд решения является декодированным информационным разрядом. Каждый считываемый разряд модифицирует адрес последующего считывания. В следующем цикле процесса, L+1, весь изложенный выше порядок повторяют снова, считывая разряды решения состояния от циклов L процесса до 1. Эта процедура продолжается в течение такого числа циклов процесса, которое необходимо для выборки нужного числа информационных разрядов для данной системы.

Конкретные примеры операций обратной последовательности проиллюстрированы на фиг.3. Если первая обратная последовательность происходит после 4 циклов процесса и оптимальным состоянием является 101 после четырех циклов процесса, то считывания, выполняемые для завершения процесса обратной последовательности, указаны как введенные данные, заштрихованные серым. Будет считано первое состояние 101 цикла 3 процесса, затем - состояние 011 цикла 2 процесса, затем - состояние 111 цикла 1 процесса, затем - состояние 110 цикла 0 процесса, что даст выходной разряд решения 0. В начале цикла 5 процесса, если оптимальным состоянием является 010, в результате первого считывания оптимальное состояние устанавливается на 101. Поэтому последующие три считывания будут следовать по тому же прежнему пути, а именно по пути введенных данных, заштрихованных серым. На этот раз выходной разряд решения считывают из введенных данных цикла 1 процесса, в результате чего разрядом решения будет 0. В начале цикла 6 процесса, если оптимальное состояние 001, в результате первого считывания оптимальное состояние устанавливается на 010. Поэтому следующие три считывания снова будут следовать по тому же прежнему пути. На этот раз выходной разряд решения считывают из введенных данных цикла 2 процесса, в результате чего разрядом решения является 1.

Обращаясь к фиг.2, в конечном счете декодер 34 формирует декодированный пакет вместе с сигналом, идентифицирующим обнаруженную скорость передачи кадров для данного пакета. Пакет с сигналом направляют в блок 43 проверки качества кадра, который проверяет отсутствие ошибок передачи или ошибок в обнаружении скорости передачи кадров. В приводимом в качестве примера варианте реализации блок 43 проверки качества кадров выполняет КЦИК, проверку частоты следования ошибок в символах и проверку показателя по Ямамото. Для выполнения проверки частоты следования ошибок в символах блок 43 проверки качества кадров повторно кодирует символы, обнаруживаемые в декодированном пакете, и сравнивает повторно кодированные символы с символами, введенными в блок проверки качества кадров, для обнаружения каких-либо различий. Для выполнения проверки показателя по Ямамото блок 43 проверки качества кадров подает принимаемые кадры в декодер решетчатого пути и определяет, приемлем ли полученный показатель. Приемлемые кадры направляют в декодер 44 речи для обратного преобразования в оцифрованные речевые сигналы. Оцифрованные речевые сигналы преобразуют в аналоговые сигналы цифроаналоговым преобразователем (не изображен) для заключительного вывода через громкоговоритель 46 мобильного телефона, в результате чего оператор телефона может слышать речевой сигнал, который был первоначально введен в общую систему по линии 11, указанной на фиг.1.

Хотя не показано, но мобильный телефон на фиг.2 может иметь дополнительные узлы для введения аналогового речевого сигнала оператором мобильного телефона и для обработки и передачи сигнала с помощью методики МДКР. Дополнительные узлы мобильного телефона могут быть аналогичны узлам, показанным на фиг.1. Также хотя не изображено, но передающая система согласно фиг.1 может иметь дополнительные узлы для приема передаваемого сигнала с мобильных телефонов и для обработки и выведения сигнала как аналогового, так и цифрового речевого сигнала, возможно, в линию КТСОП. Дополнительные узлы системы согласно фиг.1 могут быть аналогичны узлам, показанным на фиг.2.

Таким образом, важной составной частью всей системы является последовательный декодер Витерби, предназначенный для декодирования передаваемых символов. Как указано выше, декодер 34 для повышения производительности использует операцию обратной последовательности. Для значительного повышения производительности длительность обратной последовательности предпочтительно, по меньшей мере, превышает ограничивающую длительность кодера (К=9 для МДКР) от 3 до 5 раз, при лучшей производительности с большей емкостью обратной последовательности. Но чем больше длительность обратной последовательности, тем большую площадь занимают схемы и тем больше расходуется мощности для выполнения обратной последовательности. Большая площадь для схем требуется по той причине, что для запоминания разрядов решения обратной последовательности нужен больший объем памяти. Например, для кодера, ограниченного по К, по каждому информационному разряду запоминают 2^K-1 разрядов решения. Если емкость обратной последовательности равна L, то нужно запомнить L×2^K-1 разрядов. Большая мощность требуется по той причине, что для формирования одного разряда данных блок обратной последовательности должен выполнить L считываний. Также до завершения операции обратной последовательности происходит более длительная задержка. Хотя излагаемое выше описание приводится в отношении системы МДКР, использующей последовательный декодер Витерби, но аналогичные проблемы могут возникать в большинстве систем, использующих последовательные декодеры Витерби, а также соответствующие системы декодеров.

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

Сущность изобретения

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

В приводимом в качестве примера варианте реализации изобретения последовательный декодер Витерби содержит блок показателя ошибок в ветвлении, ССВ, блок обратной последовательности, содержащий ЗУПВ обратной последовательности, полную кэш-память обратной последовательности и схему контроллера обратной последовательности. Кэш-память обратной последовательности выполнена с возможностью подкачивания в кэш всех считываний. В другом приводимом в качестве примера варианте реализации изобретения полную кэш-память обратной последовательности не предусматривают. В этом варианте блок обратной последовательности вместо этого содержит L+1-разрядное ЗУПВ, реверсивный счетчик и сдвиговый регистр, выполненный с возможностью эмуляции кэш-памяти обратной последовательности. В еще одном варианте реализации изобретения L-разрядный сдвиговый регистр применяют вместо комбинации L+1-разрядного ЗУПВ и реверсивного счетчика. В разных вариантах реализации изобретения блок обратной последовательности может быть выполнен с возможностью выполнения только одного считывания обратной последовательности в каждом цикле процесса либо выполнения только m считываний обратной последовательности в каждом цикле процесса до попытки использования кэш-памяти. В других вариантах реализации изобретения блок обратной последовательности выполнен с возможностью выполнения считываний от а до b во время каждой операции обратной последовательности, причем после а считываний кэш-память проверяют по каждому последующему считыванию, пока не будет выполнено b считываний или пока не будет получено соответствие. В других вариантах реализации изобретения блок обратной последовательности выполнен с возможностью выполнения операций обратной последовательности в течение нескольких циклов процесса, а не только в одном цикле процесса. Также могут быть целесообразными сочетания признаков указанных вариантов реализации изобретения.

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

Далее следует описание вариантов реализации способа и устройства.

Краткое описание чертежей

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

фиг.1 - блок-схема, иллюстрирующая соответствующие узлы передающей системы МДКР, имеющей переменную скорость передачи;

фиг.2 - блок-схема, иллюстрирующая соответствующие узлы мобильного телефона или другой мобильной станции, принимающей сигнал, передаваемый изображаемой на фиг.1 передающей системой МДКР, и декодирующей сигнал с помощью последовательного декодера Витерби, имеющего блок обратной последовательности;

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

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

фиг.5А и 5В подробно иллюстрируют первый вариант реализации блока обратной последовательности мобильного телефона, изображаемого на фиг.4;

фиг.6А и 6В подробно иллюстрируют второй вариант реализации блока обратной последовательности мобильного телефона, изображаемого на фиг.4; и

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

Подробное описание предпочтительных вариантов реализации изобретения

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

Фиг.4 иллюстрирует соответствующие узлы мобильного телефона 128 или другой мобильной станции, принимающей передаваемый сигнал МДКР. Компоненты мобильного телефона 128 действуют аналогично мобильному телефону фиг.2 и излагаются только вкратце. Сигнал МДКР принимают антенной 130, преобразуют с понижением частоты и усиливают, если необходимо, приемником 131 и демодулируют демодулятором 132 в поток сверточно кодированных символов. Сверточно кодированные символы затем подают в модифицированный последовательный декодер 134 Витерби, который декодирует поток символов с помощью блока 136 показателя ошибок в ветвлении, ССВ 138, блока 140 обратной последовательности. Блок обратной последовательности содержит ЗУПВ 141 обратной последовательности, контроллер 142 обратной последовательности и кэш-память 145 обратной последовательности, выполненную с возможностью подкачки только считываний. Состояние с низшим показателем оптимального состояния пересылают от ССВ в блок обратной последовательности в качестве оптимального состояния, в котором его запоминают в ЗУПВ обратной последовательности и также запоминают в кэш-памяти обратной последовательности для удобства повторного обращения к нему. В соответствии с изложенным ниже декодер не должен фактически содержать полную отдельную кэш-память, как проиллюстрировано на фиг.4. Но для ясности описания общей работы системы с кэш-памятью и обратной последовательностью первоначально исходят из того, что применяется полная кэш-память.

В случае системы с кэш-памятью и обратной последовательностью согласно фиг.4 операцию обратной последовательности выполняют за счет считывания из кэш-памяти 145 обратной последовательности разряда решения, характеризующего показатель оптимального состояния, если текущий показатель оптимального состояния, подсчитанный после одного считывания в новом цикле процесса, соответствует исходному показателю оптимального состояния последнего цикла процесса. Если вновь вычисленный показатель оптимального состояния не соответствует, то тогда выполняют обычную обратную последовательность. Конкретно, в начале цикла процесса сигнал encstate устанавливают для показателя оптимального состояния. Первый разряд решения считывают из ЗУПВ обратной последовательности из местоположения, указанного сигналом encstate, и считанный разряд сдвигают в самый младший разряд encstate. Новое значение encstate затем сравнивают со значением, называемым last beststate (последнее оптимальное состояние) и содержащим показатель оптимального состояния для предыдущего цикла процесса. Если эти значения соответствуют друг другу, то нет необходимости выполнять дополнительные L-1-считывания для завершения операции обратной последовательности. Вместо этого заключительный разряд можно просто считать из кэш-памяти. (Сигналы last beststate и encstate не указаны отдельно на фиг.4, но указаны на других фигурах, поясняемых ниже.) Предположив, что должны быть выполнены дополнительные считывания L-1, блок обратной последовательности затем считывает из ЗУПВ обратной последовательности разряд решения, соответствующий значению encstate для разрядов решения, записанных во время цикла L-2 процесса. Этот процесс выполняют всего L раз, в конечном счете считывая разряд решения вычисленного encstate для цикла 0 процесса. Заключительным разрядом решения является декодированный информационный разряд. Каждый считываемый разряд модифицирует адрес последующего считывания. В следующем цикле процесса, L+1, этот порядок повторяют, считывая разряды решения о состоянии из циклов L процесса до 1. Эта процедура продолжается в течение стольких циклов процесса, сколько их необходимо для выборки нужного числа информационных разрядов для данной системы.

По завершении обычной операции обратной последовательности всю последовательность разрядов решения, сформированных обычной операцией обратной последовательности, запоминают в кэш-памяти 145 обратной последовательности, в результате чего, возможно, полную операцию обратной последовательности в следующем цикле процесса повторять будет не нужно. В частности, по завершении первого цикла процесса обратной последовательности затем в последующих циклах процесса в результате первого считывания encstate примет значение, которое он имел в начале предыдущего цикла процесса, и поэтому значение encstate будет соответствовать значению last beststate. Это происходит не всегда, но в большинстве случаев это так по причине сходимости путей сверточных кодов. Поэтому в данном цикле процесса, вероятно, что считывания L-1 будут теми же, что и в предыдущем цикле процесса, а заключительный разряд решения будет предпоследним разрядом, считанным во время предыдущего цикла процесса. Поэтому обеспечение кэш-памяти обратной последовательности обеспечивает возможность того, чтобы разряды решения для считываний L-1, включая заключительный разряд решения, просто считывались из кэш-памяти, а не вычислялись повторно, в результате чего будет повышена производительность.

При этом декодер 134 обеспечивает декодированный пакет вместе с сигналом, идентифицирующим обнаруженную скорость передачи кадров для данного пакета кадров, блок 143 проверки качества кадра, который проверяет отсутствие ошибок передачи или ошибок в обнаружении скорости передачи кадров, возникающих при применении КЦИК, проверке частоты следования ошибок символов и проверке показателя по Ямамото. Приемлемые кадры направляют в декодер 144 речи для обратного преобразования в оцифрованные речевые сигналы. Оцифрованные речевые сигналы преобразуют в аналоговые сигналы цифроаналоговым преобразователем (не изображен) для заключительного вывода их через громкоговоритель 146 мобильного телефона. Хотя это не показано, мобильный телефон фиг.4 может иметь дополнительные узлы для введения аналогового речевого сигнала от оператора мобильного телефона и для обработки и передачи сигнала с помощью методики МДКР. Дополнительные узлы мобильного телефона могут быть аналогичны узлам, изображаемым на фиг.1.

Фиг.4 иллюстрирует на высоком уровне мобильный телефон, использующий последовательный декодер Витерби, имеющий блок обратной последовательности с полной отдельной кэш-памятью обратной последовательности, выполненной с возможностью подкачки считываний. Логическая схема кэш-памяти копирует различные считанные разряды решения в своей собственной памяти. Общая экономия потребления мощности обеспечивается потому, что потребности кэш-памяти в мощности ненамного превышают уменьшение мощности, получаемое за счет более редкого обращения к ЗУПВ обратной последовательности. Также можно сократить общее время декодирования в зависимости от осуществления по сравнению с осуществлениями без применения кэш-памяти обратной последовательности. Экономия времени декодирования может быть получена в результате того, что система выполняет только одно считывание кэш-памяти, когда происходит соответствие, вместо выполнения L-1 дополнительных считываний из ЗУПВ обратной последовательности, если соответствие не возникло. Сокращение времени декодирования особенно важно в системах, в которых ЗУПВ обратной последовательности действует медленно, а кэш-память является быстродействующей.

Далее излагается приводимое в качестве примера сравнение между блоком обратной последовательности без кэш-памяти и осуществлением с блоком обратной последовательности с кэш-памятью. Для канала с установленной скоростью 1 согласно IS95, имеющего 1-процентную частоту следования ошибок в кадpax, последовательный декодер Витерби без кэш-памяти может выполнять 289 операций обратной последовательности при L=63. Необходимо отметить, что последние 72 бита пакета получают с помощью единой операции обратной последовательности. Общее число считываний ЗУПВ обратной последовательности поэтому составляет 289×63=18207. Из 100 кадров данных encstate после одного считывания соответствует beststate предыдущего цикла процесса в среднем около 233 раз из расчета на один кадр (из 289 операций обратной последовательности). Поэтому общее число нужных считываний ЗУПВ обратной последовательности с помощью блока обратной последовательности с кэш-памятью составляет только 56×63+233=3761, тем самым представляя среднюю экономию 14446 считываний на один кадр. Для канала с установленной скоростью 2 согласно IS95A, имеющего 1-процентную частоту следования ошибок в кадрах, последовательный декодер Витерби без кэш-памяти может выполнять 437 операций обратной последовательности при L=95. Необходимо отметить, что последние 104 бита пакета получают с помощью единой операции обратной последовательности. Поэтому общее число считываний ЗУПВ обратной последовательности составляет 437×95=41515. Из 23 кадров данных beststate после одного считывания соответствует beststate предыдущего цикла процесса в среднем около 338 раз из расчета на один кадр (из 437 операций обратной последовательности). Поэтому общее число нужных считываний ЗУПВ обратной последовательности с помощью блока обратной последовательности с кэш-памятью составляет только 99×95+338=9743, тем самым представляя среднюю экономию 31772 считываний на один кадр. Фактические результаты могут отличаться друг от друга в зависимости от конкретной системы.

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

Фиг.5А и 5В иллюстрируют более эффективное осуществление блока, которое может в еще большей степени сократить обращения считывания к ЗУПВ обратной последовательности за счет применения небольшого L+1-разрядного ЗУПВ или регистрового файла для запоминания разрядов решения, считываемых в каждом цикле процесса. Блок обратной последовательности содержит ЗУПВ 202 обратной последовательности, L+1-разрядное ЗУПВ 204, реверсивный счетчик 206 и сдвиговый регистр 208, взаимно подключенные к различным регистрам и логическим элементам согласно иллюстрациям. После L циклов процесса начинается первая операция обратной последовательности. Оптимальное состояние для предыдущего цикла процесса (beststate) запоминают в сдвиговом регистре 208, выходным сигналом которого является значение, упоминаемое выше как encstate. L разрядов, считанных из ЗУПВ 202 обратной последовательности, запоминают в L+1-разрядном ЗУПВ 204 (при этом запоминают дополнительный разряд для упрощения схем по сравнению с тем случаем, когда были бы запомнены только L разрядов). Отдельный регистр 210 используют для слежения за предыдущим значением beststate, которое выше упоминается как last beststate. В следующем цикле процесса новое значение beststate защелкивают в сдвиговом регистре 208. В результате первого считывания цикла процесса получают разряд решения, который сдвигают в самый младший разряд сдвигового регистра 208. Этот разряд также запоминают в L+1-разрядном ЗУПВ 204, как в предшествующем случае. Если теперь encstate соответствует last beststate, тогда разряд из наименьшего/старейшего цикла процесса выводят из L+1-разрядного ЗУПВ 204, и тем самым он становится выходным разрядом. Этот разряд является тем же разрядом, который был бы получен при выполнении полной операции обратной последовательности на ЗУПВ обратной последовательности, просто в этом случае его получают с меньшим временем обработки и за счет меньшего объема работы. Если после одного считывания encstate не соответствует last beststate, то выполняют полную операцию обратной последовательности, одновременно заполняя L-1 местоположений L+1-разрядного ЗУПВ 204. И в том, и в другом случаях в конце цикла процесса предыдущее значение beststate запоминают в last beststate, и последующий процесс идет аналогичным образом именно как описываемый здесь процесс. За счет выполнения блока обратной последовательности с L+1-разрядным ЗУПВ для ЗУПВ обратной последовательности требуется меньшее число операций считывания, в результате чего потребление мощности всем декодером снижается.

Осуществление согласно фиг.5А и 5В может показаться несколько сложным, но по сравнению с осуществлением, имеющим блок обратной последовательности с кэш-памятью, к которой обращаются в каждом цикле процесса, блок обратной последовательности согласно фиг.5А и 5В требуется дополнить только реверсивным счетчиком 206, L+1-разрядным ЗУПВ 204 (или другим регистровым файлом), и различными едиными одноразрядными регистрами и комбинаторной логикой, как показано на указанных фиг. Преимущество такого блока заключается в том, что в циклах процесса с соответствием необходимо только одно считывание с помощью ЗУПВ обратной последовательности, а не L считываний, и также одно считывание и запись L+1-разрядного ЗУПВ, что относительно несущественно. В случае несоответствий цикла процесса необходимо сделать L считываний с помощью ЗУПВ обратной последовательности и также L записей в L+1-разрядный ЗУПВ. Для этих записей не требуется значительное потребление мощности, поскольку размер памяти небольшой и поскольку частота несоответствий обычно остается небольшой. Если используется регистровый файл, то эти записи могут экономить мощность в еще большей степени.

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

- reset - общий сигнал возвращения в исходное положение (сброс) для возвращения в исходное положение некоторых логических схем.

- beststate - этот сигнал получают из ССВ 138 (фиг.4), и он указывает состояние с наименьшим показателем ошибок для последнего цикла процесса. Сигнал beststate изменяется до формирования start chainback и после формирования done chainback.

- decision bit - формируется в ССВ. Это данные, подлежащие запоминанию в ЗУПВ обратной последовательности.

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

- done chainback - формируется в конце цикла процесса по завершении операции обратной последовательности.

- enable cache read - разрешает использование небольшого L+1-разрядного ЗУПВ или регистрового файла для получения выходного разряда. Сигнал enable cache read формируется для 1 цикла синхроимпульса одновременно с первым импульсом cbread каждого цикла процесса.

- cbread - формируется L раз в каждом цикле процесса для выполнения L считываний из ЗУПВ обратной последовательности. Первый сигнал формируется после start chainback, последний - до done chainback. Если имеется согласование, то будет выполняться только первое считывание, а остальные считывания будут маскированы схемой.

- cbwrite - формируется всякий раз, когда разряд решения готов для запоминания в ЗУПВ обратной последовательности.

- chram addr - обычный адрес, который приводит в действие ЗУПВ обратной последовательности. Для дополнительной экономии мощности эти шины можно маскировать и оставлять статичными при пропуске остальных L-1 считываний ЗУПВ обратной последовательности.

- do compare - внутренний сигнал, указывающий, что будут рассмотрены результаты компаратора, т.е. блок обратной последовательности сравнивает текущее значение encstate с beststate последнего цикла процесса, запомненного как last beststate, и определяет, имеется ли соответствие.

- match - внутренний сигнал, который указывает, что текущее значение encstate соответствует last beststate предыдущего цикла процесса.

- mismatch - внутренний сигнал, который указывает, что после первого считывания с помощью ЗУПВ обратной последовательности encstate не соответствовал last beststate.

- cbread muxed - внутренний сигнал, напоминающий сигнал cbread, но его отличие в том, что его маскируют при выполнении соответствия.

- read last bit - внутренний сигнал, который применяют для защелкивания выходного разряда из L+1-разрядного ЗУПВ в регистр.

- chram dout - внутренний сигнал, который является разрядом считывания из ЗУПВ обратной последовательности.

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

Фиг.6А и 6В иллюстрируют осуществление, аналогичное осуществлению согласно фиг.5А и 5В, но в этом случае вместо комбинации L+1-разрядного ЗУПВ и реверсивного счетчика применяют L-разрядный сдвиговый регистр. В частности, блок обратной последовательности согласно фиг.6А и 6В содержит ЗУПВ 302 обратной последовательности, L-разрядный сдвиговый регистр 305 и сдвиговый регистр 308, взаимно подключенные вместе к различным регистрам и логическим элементам, как показано на указанных фигурах. После первого считывания в цикле процесса считанный разряд сдвигают в сдвиговый регистр 308, выходным сигналом которого является encstate. Если encstate теперь соответствует last beststate, то считанный разряд сдвигают в самый старший разряд L-разрядного сдвигового регистра, а самым младшим разрядом L-разрядного сдвигового регистра является выходной разряд, который был бы получен операцией обратной последовательности. Если encstate не соответствует last beststate, то считанный разряд сдвигают в самый младший разряд L-разрядного сдвигового регистра, а остальные L-1 считанные разряды сдвигают также в самый младший разряд.

Следует отметить, что L-разрядный сдвиговый регистр должен быть выполнен с возможностью сдвига в обоих направлениях, т.е. L-разрядный сдвиговый регистр согласно фиг.6А и 6В отличается от стандартного сдвигового регистра тем, что содержит дополнительный ввод слева, который определяет направление сдвига. Также для каждого разряда, считанного из ЗУПВ обратной последовательности, все L разрядов необходимо сдвинуть сразу, в результате чего может возрасти потребление мощности по сравнению с осуществлением согласно фиг.5А и 5В. В другом осуществлении (не изображено) потребление мощности также снижают за счет введения декодирующей логической схемы, чтобы выбирать каждый разряд отдельно, при этом каждый разряд сдвигового регистра загружают отдельно. Затем, при запоминании L разрядов, запоминание выполняют путем загрузки каждого разряда отдельно. Поэтому регистру нужно только совершить сдвиг при возникновении соответствия (один раз на один цикл процесса), тем самым снижая потребление мощности. В других осуществлениях обеспечивают схему для проверки соответствий после двух или более считываний цикла процесса, чтобы в еще большей степени повысить вероятность соответствия, тем самым в еще большей степени сокращая время декодирования и уменьшая потребление мощности. Эту схему можно использовать в осуществлениях согласно фиг.5А и 5В или 6А и 6В и также в других осуществлениях.

В описываемых выше осуществлениях схемы блока обратной последовательности действуют в каждом цикле процесса для выполнения одного считывания обратной последовательности до того, как решить, использовать ли кэш-память или нет, чтобы завершить операцию обратной последовательности. Фиг.7 иллюстрирует альтернативное осуществление, согласно которому m считываний обратной последовательности выполняют в каждом цикле процесса до того, как решить, использовать ли кэш-память или нет, чтобы завершить операцию обратной последовательности. В частности, фиг.7 иллюстрирует схему, применяемую для формирования сигнала match на основе m считываний. Схемы согласно фиг.7 можно применить в блоках обратной последовательности с кэш-памятью согласно либо фиг.5А и 5В, либо фиг.6А и 6В в качестве изображаемой в них замены соответствующей схемы формирования сигнала match. Схема match согласно фиг.7 действует в цикле процесса для выполнения m считываний обратной последовательности и затем для сравнения текущего значения encstate с encstate, запомненным после m-1 считываний во время предыдущего цикла процесса. В этом осуществлении сигнал enable cache read синхронизируют таким образом, что он формируется одновременно с м-ным считыванием обратной последовательности. Также вместо запоминания значения beststate в начале каждой операции обратной последовательности значение encstate запоминают после m-1 считываний. Конкретный выбор m предполагает компромисс между числом считываний (m), требуемым для каждого цикла процесса, и вероятностью соответствия. Более крупное значение m повышает вероятность соответствия после m считываний. Необходимо отметить, что изображаемая на фиг.7 схема принимает дополнительный сигнал save state для использования при защелкивании encstate после m-1 считываний. Также сигнал do compare несколько отличается от излагаемого выше описания, поскольку он формируется после m считываний вместо формирования после одного считывания, и его используют также для защелкивания в значении encstate, защелкнутом во время предыдущего считывания, и поэтому его можно сравнивать в следующем цикле процесса.

В еще одном еще более общем варианте реализации вместо проверки значения encstate после 1 или m считываний в каждом цикле процесса encstate сравнивают со значением encstate, запомненным во время предыдущего цикла процесса после выполнения а-1 считываний, затем после следующего считывания (а+1) encstate сравнивают со значением encstate, запомненным в предыдущем цикле процесса после совершения а считываний и т.д., пока не будет выполнено b считываний в этом цикле процесса. В этом осуществлении значения encstate в b-а+1 состояниях запоминают предпочтительно с помощью сдвигового регистра. Каждое последующее значение encstate просто является сдвигом влево предыдущего значения encstate с новым самым младшим разрядом. Сигнал enable cacne read утверждается в некоторой совокупности считываний обратной последовательности, останавливаясь после b считываний или при обнаружении соответствия. Выбор а и b позволяет компромиссы с точки зрения упрощения и экономии на потреблении мощности. Осуществления согласно фиг.5А и 5В или фиг.6А и 6В соответствуют случаю, когда а=1 и b=1 при выполнении одного считывания, и поэтому схема быстро принимает решение о факте наличия или отсутствия соответствия. Описываемое выше осуществление, согласно которому выполняют m считываний, соответствует случаю, когда a=m, b=m и когда для выполнения сравнения нужно сделать m считываний.

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

В других осуществлениях операции обратной последовательности выполняют по нескольким циклам процесса. В описываемых выше осуществлениях для ясности описания изобретения предполагалось, что в каждом цикле процесса выполняется 1 операция обратной последовательности. Но каждое осуществление можно модифицировать для выполнения операций обратной последовательности из расчета выполнения одной операции в течение нескольких циклов процесса. Например, в осуществлении, когда операция обратной последовательности происходит каждые 4 цикла процесса и когда результат этой операции заключается в получении 4 декодированных разрядов, тогда сигнал enable cache read можно формировать только при 4-ом считывании обратной последовательности. Но нет необходимости, чтобы такая система была обязательно выполнена с возможностью иметь сигнал enable cache read только на 4-м считывании обратной последовательности. Напротив, даже если операция обратной последовательности осуществлена по 4 циклам процесса, то решение о времени сравнения encstate все еще может зависеть от значений а и b. В этом отношении enable cache read можно было бы утверждать 4 раза, если бы соответствие давало 4 разряда декодированных данных, считываемых из кэш-памяти. Несколько иное осуществление производит обработку с помощью 4-разрядных групп (или с помощью групп любого другого соответствующего размера). Поэтому, когда выполняется операция обратной последовательности, система после 4 (четырех) считываний проверяет, имеет ли место соответствие. Если имеет, то система считывает последние 4 разряда кэш-памяти и выводит их, в ином случае система продолжает выполнение обратной последовательности и запоминает последние 4 считывания из ЗУПВ обратной последовательности.

Многие из описываемых выше осуществлений относятся к системам, имеющим каналы информационного обмена, в которых обрабатывают информацию, передаваемую в виде пакетов, т.е. блок данных подвергают сверточному кодированию, и в конце добавляют конечные нули, чтобы установить в исходное состояние кодер между всеми пакетами. В результате этого система ждет, пока не пройдет L+K циклов, затем начинает обратную последовательность и потом, в заключение, система выполняет одну конечную операцию обратной последовательности с получением L+K разрядов. Прочие осуществления изобретения соответствуют информационным каналам, в которых информация не представлена в виде пакетов, например, каналам синхронизации или поискового вызова, определяемым согласно нормативу IS95. Для каналов трафика, в которых данные не сформированы в виде пакетов, данные группируют в кадры, но состояние кодера не устанавливают в исходное состояние между всеми кадрами. Поэтому кодер выполняет операцию обратной последовательности каждый цикл процесса. Необходимо отметить, что принципы данного изобретения можно применить почти в любом последовательном декодере Витерби независимо от типа канала всей системы.

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

Формула изобретения

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

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

3. Последовательный декодер Витерби по п.2, отличающийся тем, что а равно m и b равно m, причем m представляет собой количество считываний обратной последовательности в каждом цикле процесса до попытки использования кэш-памяти.

4. Последовательный декодер Витерби по п.2, отличающийся тем, что а равно 1 и b равно 1.

5. Последовательный декодер Витерби, содержащий приемник, выполненный с возможностью приема сверточно кодированного потока символов, схему суммирования-сравнения-выбора, выполненную с возможностью формирования совокупности разрядов решения из сверточного кодированного потока символов в течение каждого цикла из числа совокупности циклов процесса, модуль, включающий в себя память, выполненную с возможностью запоминания указанной совокупности разрядов решения для каждого цикла из числа указанной совокупности циклов процесса, причем схема суммирования-сравнения-выбора формирует в течение каждого нового цикла процесса разряд решения, характеризующий показатель оптимального состояния, начиная с текущего исходного показателя оптимального состояния, и затем выполняет последующую операцию обратной последовательности по совокупности запомненных разрядов решения в памяти обратной последовательности в каждом цикле из числа указанной совокупности циклов процесса, кэш-память, подключенную к указанной памяти и предназначенную для запоминания некоторой последовательности разрядов решения, к которым осуществлено обращение в течение предыдущего цикла обратной последовательности, и для выведения разряда решения, который был сформирован в ином случае, причем кэш-память содержит регистр сдвига влево для приема показателя оптимального состояния для текущего цикла процесса и L+1-разрядное запоминающее устройство с произвольной выборкой (ЗУПВ) для запоминания последовательности разрядов решения, к которым осуществлено обращение в течение предыдущей операции обратной последовательности, причем L является длительностью обратной последовательности.

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

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

8. Последовательный декодер Витерби, содержащий приемник, выполненный с возможностью приема сверточно кодированного потока символов, схему суммирования-сравнения-выбора, выполненную с возможностью формирования совокупности разрядов решения из сверточно кодированного потока символов в течение каждого цикла из числа совокупности циклов процесса, модуль, включающий в себя память, выполненную с возможностью запоминания указанной совокупности разрядов решения для каждого цикла из числа указанной совокупности циклов процесса, причем схема суммирования-сравнения-выбора формирует в течение каждого нового цикла процесса разряд решения, характеризующий показатель оптимального состояния, начиная с текущего исходного показателя оптимального состояния, и затем выполняет последующую операцию обратной последовательности по совокупности запомненных разрядов решения в памяти обратной последовательности в каждом цикле из числа указанной совокупности циклов процесса, кэш-память, подключенную к указанной памяти и предназначенную для запоминания некоторой последовательности разрядов решения, к которым осуществлено обращение в течение предыдущего цикла обратной последовательности, и для выведения разряда решения, который был бы сформирован в ином случае, причем кэш-память содержит регистр сдвига влево для сдвига в показателе оптимального состояния для текущего цикла процесса, некоторую совокупность последовательных регистров для запоминания ранее сдвинутых вариантов показателя оптимального состояния, компаратор для сравнения выходного сигнала регистра сдвига влево с выходным сигналом последнего регистра из числа указанной совокупности последовательных регистров и, если имеется соответствие, для выведения сигнала соответствия, L+1-разрядное запоминающее устройство с произвольной выборкой (ЗУПВ) для запоминания последовательности разрядов решения, обращение к которым осуществлено в течение предыдущей операции обратной последовательности, при этом L является длительностью обратной последовательности, и выходную схему, подключенную к L+1-разрядному ЗУПВ и к компаратору, для приема сигнала соответствия от компаратора и для управления L+1-разрядным ЗУПВ для выведения запомненного в нем самого раннего разряда решения.

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

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

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

12. Способ по п.11, отличающийся тем, что а равно m и b равно m.

13. Способ по п.11, отличающийся тем, что а равно 1 и b равно 1.

РИСУНКИРисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9