СПОСОБ И УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ СОСТОЯНИЯ МАКСИМАЛЬНОГО ПРАВДОПОДОБИЯ В ДЕКОДИРУЮЩЕМ УСТРОЙСТВЕ Российский патент 2004 года по МПК H04B7/24 

1. Область техники.

Изобретение относится к системам связи, таким как спутниковые системы, цифровые системы с интеграцией служб (ISDN), цифровые сотовые системы, широкополосные системы многостанционного доступа с кодовым разделением каналов типа W-CDMA и системы связи типа IMT-2000, в частности к устройству и способу для выбора (или определения) состояния максимального правдоподобия (МП) в декодирующем устройстве.

2. Описание предшествующего уровня техники.

Настоящее изобретение может применяться с алгоритмом Витерби, который используется в декодере Витерби, корректоре Витерби, детекторе МП последовательности, турбодекодере, декодере с программируемым вводом и выводом (ПВВ) и в модуляторе с решетчатым кодированием (МРК).

В частности, изобретение может быть использовано в дополнительном канале (или информационном канале) интерфейса радиосвязи системы IMT-2000 и в турбодекодере, который будет применяться в информационном канале системы UMTS (Универсальные мобильные системы связи), предложенной Европейским институтом стандартов в области телекоммуникаций. Кроме того, изобретение позволяет повысить надежность системы цифровой связи и, в частности, улучшить рабочие характеристики существующих и будущих цифровых систем мобильной связи.

Обычно для определения МП состояний используется метод обратного прослеживания. Этот метод заключается в вычислении вектора для минимизации евклидова расстояния между символьным вектором R=(r1, r2,..., rn), принятым во время декодирования по Витерби, и кодовым вектором С=(с1, с2,,..., cn) на решетке кодера, и последующей выдаче МП состояния на соответствующей ветви в требуемое время при обратном прослеживании состояний по пути (маршруту) решетки, вдоль которого проходит кодовый вектор, начиная с текущего момента времени. Например, для определения МП состояния в текущий момент времени k необходимо выполнить операцию сложения-сравнения-выбора (ССВ) и выбора пути в декодере Витерби до наступления момента времени, которое является временем (k+W), опережающим текущий момент времени, и проследить МП путь назад на W, начиная с момента времени (k+W). В данном случае W является заданной величиной и имеет значение W>5m, где m - размер (или емкость) памяти сверточного кодера. W представляет собой скользящее окно, а размер памяти m равен 8 в случае длины кодового ограничения К=9.

Метод обратного прослеживания имеет ряд недостатков при его применении в высокоскоростном декодерe Витерби. Использование метода обратного прослеживания создает значительную задержку. Например, при глубине декодирования или глубине скользящего окна, равной W, необходимо выполнять обратный поиск на W для выбора МП состояния. Следовательно, если общий размер кадра равен FL, то задержка на обработку, необходимая для всего поиска МП состояния, увеличивается в Wx(FL-W) раз. Следует отметить, что эта задержка на обработку значительно возрастает по сравнению с задержкой на обработку L, имеющей место, когда декодер Витерби выполняет операцию обратного прослеживания только один раз (т. е. когда декодер Витерби работает в кадровом режиме (W= FL)). Точнее, задержка возрастает в (W(FL-W)-FL) раз. Например, при FL=2000 и W=60 задержка на обработку для поиска МП состояния в кадровом режиме будет равна 2000, что равно FL. Однако в режиме скользящего окна задержка на обработку на поиск МП состояния равна W(FL-W)=60(2000-60)=116400, что в 58,2 раз больше задержки на обработку в кадровом режиме. Таким образом, отмечено, что задержка на обработку возрастает приблизительно в W раз. Следовательно, в известных решениях при поиске МП состояния требуется задержка на обработку большого числа внутренних операций.

Для использования в качестве турбодекодера предлагались разные декодеры, такие как декодер максимума апостериорной вероятности (декодер МАВ) и декодер с алгоритмом Витерби с программируемым выводом (декодер АВПВ). Для улучшения рабочих характеристик декодера АВПВ требуется алгоритм для поиска МП состояния. Низкоскоростной турбокодер можно реализовать, применяя описанный выше метод обратного прослеживания. Однако, поскольку турбодекодер очень сложен в реализации, поиск МП состояния методом обратного прослеживания можно выполнять только при относительно низкой скорости передачи данных.

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

Прежде всего, метод обратного прослеживания имеет значительную задержку при определении МП состояния. Например, при глубине декодирования (или глубине скользящего окна), равной W, требуется выполнять обратный поиск W раз, чтобы найти МП состояние в каждом процессе обратного прослеживания. Следовательно, если полный размер кадра равен FL, задержка на обработку, необходимая для всего поиска МП состояния, значительно возрастает в W(FL-W) раз.

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

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

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

Задачей изобретения является создание устройства и способа для определения МП состояния в декодирующем устройстве с использованием метода решетчатого декодирования.

Еще одной задачей изобретения является создание устройства и способа для определения МП состояния в декодере АВПВ.

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

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

Указанные выше и другие задачи, признаки и преимущества настоящего изобретения поясняются в последующем подробном описании со ссылками на чертежи, на которых представлено следующее:
фиг. 1 - иллюстрация способа перестановки регистров согласно варианту осуществления настоящего изобретения,
фиг. 2 - ячейка перестановки регистров согласно варианту осуществления настоящего изобретения,
фиг.3 - селектор МП состояния согласно варианту осуществления настоящего изобретения,
фиг. 4 - решетчатая схема кодера с длиной кодового ограничения К=2 и скоростью кодирования R=1/2,
фиг.5 - решетчатая схема турбокодера с К=4, используемого для интерфейса IMT-2000,
фиг. 6 - селектор МП состояния для турбокодера с К=4, используемого для интерфейса IMT-2000, согласно варианту осуществления настоящего изобретения.

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

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

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

В данном варианте осуществления изобретения имеется блок выбора пути и блок ячеек перестановки регистров. Блок выбора пути вычисляет метрику ветви (MB) в каждом возможном состоянии из принятых из канала символов и обеспечивает блок ячеек перестановки регистров ячейкой сигнала выбора пути одного из двух сигналов, введенных в каждую ячейку перестановки регистров. Блок ячеек перестановки регистров обновляет значения состояния, хранимые в ячейках, путем перестановки между рядами в соответствии с сигналом выбора пути. Если этот процесс перестановки выполняется в течение заданного времени, значения состояния, хранимые в одном и том же столбце, будут иметь одинаковое значение. В данном случае одинаковое значение состояния идентично МП состоянию, полученному в решетчатом декодере.

В данном контексте понятие "блок ячеек перестановки регистров" используется взаимозаменяемо с понятием "селектор МП состояния".

На фиг.1 изображен блок ячеек перестановки регистров согласно одному из вариантов осуществления настоящего изобретения. Изображенный на фиг.1 блок ячеек перестановки регистров включает в себя множество ячеек, расположенных в виде матрицы из рядов и столбцов. Количество рядов равно количеству состояний (S=4) решетки, а количество столбцов равно размеру (W) данного окна. Каждая ячейка представляет собой ячейку памяти для хранения значения состояния решетки. Комбинация ячеек в каждом ряду будет именоваться как память пути. Следовательно, при количестве состояний S=4 и размере W памяти пути, соответствующей каждому состоянию, общий размер блока ячеек перестановки регистров будет равен W•S(=4).

При этом предполагается, что нижний путь из двух путей, введенных в состоянии 0 в момент времени t, определяется как МП путь (при этом в решетке верхнее состояние равно 0, а следующие состояния последовательно равны 1, 2 и 3), это означает, что ячейка "состояние 1" в момент времени t+1 передает содержимое данных, выбранных при предыдущем определении МП пути, в ячейку "состояние 0" в момент времени t в ячейке перестановки регистров. Следовательно, в блоке ячеек перестановки регистров все биты данных, хранимые в памяти пути во втором ряду, передаются в память пути в первом ряду, за исключением крайней левой ячейки. Крайняя левая ячейка в первом ряду выбирает сигнал b нижнего порта, определенный согласно решетчатой структуре. Следовательно, как показано на чертеже, все биты данных во втором ряду передаются в первый ряд. Последнее выбранное содержимое запоминается в крайней левой ячейке первого ряда. Например, информация, сохраненная в крайней левой ячейке первого ряда в момент времени k будет 'b', поскольку выбран нижний путь в решетке, показанной справа. Значение, сохраненное в последней ячейке первой линии, такое же, как значения, хранимые в другой линии последнего столбца, если размер окна достаточно велик. Это значение является индексом МП состояния в момент t-W+2.

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

Как показано на фиг.2, если выбирается верхний путь из путей, введенных в состояние '0' в данный момент времени k, блок ячеек перестановки регистров сдвигает вправо биты данных в ячейках первого ряда на одну ячейку и сохраняет 'а' в крайней левой ячейке первого ряда. Если же выбран нижний путь из путей, введенных в состояние '0', блок ячеек перестановки регистров передает биты данных в ячейках второго ряда в первый ряд и сохраняет 'b' в крайней левой ячейке первого ряда.

Если выбран верхний путь из путей, введенных в состояние '1', блок ячеек перестановки регистров передает биты данных в ячейках третьего ряда во второй ряд и сохраняет 'а' в крайней левой ячейке второго ряда. Если же выбран нижний путь, блок ячеек перестановки регистров передает биты данных в ячейках четвертого ряда в первый ряд и запоминает 'b' в крайней левой ячейке второго ряда.

Если выбран верхний путь из путей, введенных в состояние '2', блок ячеек перестановки регистров передает биты данных в ячейках первого ряда в третий ряд и запоминает 'с' в крайней левой ячейке третьего ряда. Если же выбран нижний путь из путей, введенных в состояние '2', блок ячеек перестановки регистров передает биты данных в ячейках второго ряда в третий ряд и запоминает 'd' в крайней левой ячейке третьего ряда.

Если выбран верхний путь из путей, введенных в состояние '3', блок ячеек перестановки регистров передает биты данных в ячейках третьего ряда в четвертый ряд и запоминает 'с' в крайней левой ячейке четвертого ряда. А если выбран нижний путь из путей, введенных в состояние '3', блок ячеек перестановки регистров сдвигает биты данных в ячейках четвертого ряда вправо на одну ячейку и запоминает 'd' в крайней левой ячейке четвертого ряда. Описанный выше выбор пути выполняется путем вычисления метрик ветви и пути в блоке выбора пути. Кроме того, каждая ячейка, принимающая два бита данных, представляет собой умножитель 2x1 для выбора одного из двух введенных битов данных. Блок выбора пути подает в мультиплексор управляющий сигнал (или сигнал выбора пути (0 или 1)).

Далее описывается осуществление способа определения МП состояния в блоке ячеек перестановки регистров.

В каждом состоянии данные, хранимые в ячейках, обновляются в ответ на сигнал выбора пути, поступивший из блока выбора пути. При этом данные сохраняются в ячейках независимо от формата. Иными словами, хотя преобразование выполняется для данных, выраженных как {a, b, c, d}, оно не зависит от МП пути, и только выходное состояние, соответствующее МП пути, преобразуется иным образом. Следовательно, если соответствующие индексы состояния 0, 1, 2 или 3 решетки согласованы соответственно с {a, b, c, d}, то значения, выданные из блока ячеек перестановки регистров, станут значениями индексов состояния для МП пути. При этом, если символы согласованы с данными, выраженными как {a, b, c, d}, блок ячеек перестановки регистров будет декодером Витерби. Однако данный вариант изобретения преобразует значения индексов состояния решетки для данных, выраженных как {a, b, c, d}, и обновляет содержимое, хранящееся в соответствующих ячейках, в соответствии с сигналом выбора пути, чтобы определить МП состояние.

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

Как видно на фиг.3, блок выбора пути вычисляет метрику ветви из принятого вектора для каждого состояния в момент времени k, как это делается в декодере Витерби. Затем блок выбора пути определяет метрику пути из метрики ветви и определяет один путь в каждом состоянии путем операции ССВ. После этого блок выбора пути выдает сигнал выбора пути в блок ячеек перестановки регистров через определенный путь. Например, при количестве состояний S=4 блок выбора пути выдает параллельно 4 бита, как показано на чертеже. Блок ячеек перестановки регистров затем обновляет содержимое ячеек в соответствии с сигналом выбора пути. Например, если сигнал выбора пути '0000', то значения индекса состояния, хранимые в соответствующих ячейках первого ряда, сдвигаются вправо на одну ячейку согласно первому сигналу выбора PS0='0'; значения индекса состояния, хранимые в соответствующих ячейках третьего ряда, передаются в следующую ячейку второго ряда в соответствии со вторым сигналом выбора PS1='0'; значения индекса состояния, хранимые в соответствующих ячейках первого ряда, передаются в следующую ячейку третьего ряда в соответствии с третьим сигналом выбора PS2='0', и значения индекса состояния, хранимые в соответствующих ячейках третьего ряда, передаются в следующую ячейку четвертого ряда в соответствии с четвертым сигналом выбора PS3= '0'.

На фиг.4 показана схема решетки кодера с количеством состояний S=4. При этом информация индекса МП состояния -{0, 1, 2, 3, 1, 2, 1, 0, 2...}. В приведенной ниже таблице показана информация индекса МП состояния, хранимая в соответствующих ячейках блока ячеек перестановки регистров, имеющих соединение согласно решетчатой структуре, показанной на фиг.4.

В таблице, например, для информации индекса МП состояния, хранимой в соответствующих ячейках в момент времени @Т7, исходное значение '0202' хранится в k-ом столбце, а значение индекса состояния '1111', которое является информацией индекса предыдущего МП состояния, хранится в (k-1)-ом столбце. То есть, информация состояния, хранимая в течение времени от (k-6) до (k-1), представляет '0000', '2222', '3333', '1111', '2222' и '1111' соответственно, что идентично последовательности {0, 2, 3, 1, 2, 1} состояний МП в решетке на фиг. 4. Следовательно, при выполнении операции выбора МП состояния в какой-то мере можно получить информацию индекса МП состояния при каждом обновлении ячейки. Это значит, что по сравнению с известным методом обратного прослеживания можно непрерывно получать информацию индекса МП состояния непосредственно после выполнения какой-то части операции выбора МП состояния, тем самым уменьшая задержку на обработку. Кроме того, при выполнении операции выбора информации индекса МП состояния в какой-то мере значения состояния, хранимые в том же самом столбце, становятся идентичными, что позволяет вывести информацию индекса состояния МП в любой ячейке. Если значения индексов, хранимые в одном и том же столбце, различные, выводится информация состояния, имеющая большее число.

На фиг.5 показана решетчатая структура для турбокодера с К=4 и порождающим многочленом обратной связи d(D)1+d2+d3 (знак означает умножение), используемого для интерфейса радиосвязи IMT-2000. Как видно на фиг.5, поскольку К=4, существует всего 8 состояний, и поскольку R=1/3, каждая ветвь выдает три символа С0, С1 и С2. В состоянии 0 (S0; 000) при введенной информации 0 переход происходит в состояние 0 (S0; 000), а при введенной информации 1 переход происходит в состояние 4 (S4; 100). В состоянии 1 (S1; 001) при введенной информации 0 переход происходит в состояние 4 (S4; 100), а при введенной информации 1 переход происходит в состояние 0 (S0; 000). В состоянии 2 (S2; 010) при введенной информации 0 переход происходит в состояние 5 (S5; 101), а при введенной информации 1 переход происходит в состояние 1 (S1; 001). В состоянии 3 (S3; 011) при введенной информации 0 переход происходит в состояние 1 (S1; 001), а при введенной информации 1 переход происходит в состояние 5 (S5; 101). В состоянии 4 (S4; 100) при введенной информации 0 переход происходит в состояние 2 (S2; 010), а при введенной информации 1 переход происходит в состояние 6 (S6; 110). В состоянии 5 (S5; 101) при введенной информации 0 переход происходит в состояние 6 (S6; 110), а при введенной информации 1 переход происходит в состояние 3 (S3; 011). В состоянии 6 (S6; 110) при введенной информации 0 переход происходит в состояние 7 (S7; 111), а при введенной информации 1 переход происходит в состояние 3 (S3; 011). В состоянии 7 (S7; 111) при введенной информации 0 переход происходит в состояние 3 (S3; 011), а при введенной информации 1 переход происходит в состояние 7 (S7; 111).

На фиг. 6 показана структура блока ячеек перестановки регистров, соответствующая структуре решетки на фиг.5. На фиг.6 ввод {1, 2, 3, 4, 5, 6, 7} в соответствующие ячейки показывает состояния 0, 1, 2, 3, 4, 5, 6 и 7 в решетке, а РS0-РS7 показывают сигналы выбора пути для выбора рядов, поступающие из блока выбора пути. Размер окна W (или Ds) определяется экспериментальным путем. Ввод информации состояния в соответствующие ячейки в первом столбце предварительно определяется решеткой. Кроме того, каждая из ячеек, имеющихся между первым столбцом и последним столбцом, соединена с двумя ячейками в непосредственно предшествующем столбце, так что они принимают два значения состояния согласно решетчатой структуре. Например, каждая ячейка, за исключением первой ячейки в первом ряду, соединена с непосредственно предшествующей ячейкой в том же самом ряду и второй ячейкой во втором ряду непосредственно предшествующего столбца. Каждая ячейка не всегда принимает два значения состояния, как показано на фиг.6. То есть, каждая ячейка может принимать два или более значений состояния в зависимости от характеристик кодера. При приеме двух значений состояния каждая ячейка имеет структуру умножителя 2x1, как показано на чертеже, и выбирает одно из двух принятых значений состояния в соответствии с сигналом выбора пути для выдачи выбранного значения состояния в соответствующую ячейку.

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

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

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

1. Устройство для выбора состояния максимального правдоподобия (МП) в декодирующем устройстве, содержащее множество ячеек, расположенных в виде матрицы из рядов и столбцов, и множество линий выбора пути, каждая из которых соединена со всеми ячейками в соответствующем ряду, при этом линии выбора пути принимают связанные с ними сигналы выбора пути, каждая ячейка в столбце соединена с двумя ячейками в непосредственно предшествующем столбце для приема двух значений состояния соответственно решетчатой структуре, при этом ячейка принимает множество значений состояния в соответствии с заданной решетчатой структурой декодирующего устройства, каждая ячейка первого столбца принимает множество значений состояния, определенных в соответствии с решетчатой структурой кодера, упомянутая каждая ячейка первого столбца выбирает одно из принятых значений состояния в ответ на сигнал выбора для сохранения выбранного значения состояния и ячейки в последнем столбце выдают значение состояния, соответствующее МП состоянию.2. Устройство по п.1, отличающееся тем, что каждая ячейка содержит mx1 мультиплексор.3. Устройство по п.1, отличающееся тем, что значения состояния, хранимые в ячейках одного и того же столбца, становятся одинаковыми после истечения заданного времени.4. Устройство по п.1, отличающееся тем, что если значения состояния, выданные из ячеек последнего столбца, различаются, в качестве значения МП состояния выбирается значение состояния, имеющее большее число.5. Устройство по п.1, отличающееся тем, что сигнал выбора пути является сигналом для вычисления значения метрики ветви в каждом состоянии решетки кодера и для выбора пути с использованием вычисленных значений метрики ветви и значения метрики непосредственно предшествующего пути.6. Устройство для выбора состояния максимального правдоподобия (МП) в декодирующем устройстве, содержащее блок выбора пути для вычисления значения метрики ветви для каждой ветви в каждом состоянии решетки, определенной кодером, и выдачи сигналов выбора пути для выбора пути с использованием вычисленных значений метрики ветви и значения метрики непосредственно предшествующего пути, и блок перестановки регистров, включающий множество ячеек, расположенных в виде матрицы из рядов и столбцов, и множество линий выбора пути, каждая из которых соединена со всеми ячейками в соответствующем ряду, при этом линии выбора пути принимают связанные с ними сигналы выбора пути, каждая ячейка в столбце соединена с двумя ячейками в непосредственно предшествующем столбце для приема двух значений состояния соответственно заданной решетчатой структуре, при этом ячейка принимает множество значений состояния в соответствии с решетчатой структурой декодирующего устройства, каждая ячейка в первом столбце принимает множество значений состояния, определенных в соответствии с решетчатой структурой кодера, упомянутая каждая ячейка первого столбца выбирает одно из принятых значений состояния в ответ на сигнал выбора для сохранения выбранного значения состояния и ячейки в последнем столбце выдают значение состояния, соответствующее МП состоянию.7. Устройство по п.6, отличающееся тем, что каждая ячейка содержит mx1 мультиплексор.8. Устройство по п.6, отличающееся тем, что значения состояния, хранимые в ячейках одного и того же столбца, становятся одинаковыми после истечения заданного времени.9. Устройство по п.6, отличающееся тем, что если значения состояния, выданные из ячеек последнего столбца, различаются, то в качестве значения МП состояния выбирается значение состояния, имеющее большее число.10. Способ выбора состояния максимального правдоподобия (МП) в устройстве поиска МП состояния, содержащем множество ячеек, расположенных в виде матрицы из рядов и столбцов, и множество линий выбора пути, каждая из которых соединена со всеми ячейками в соответствующем ряду, при этом линии выбора пути принимают связанные с ними сигналы выбора пути, каждая ячейка в столбце соединена с двумя ячейками, в непосредственно предшествующем столбце для приема двух значений состояния соответственно заданной решетчатой структуре, при этом ячейка принимает множество значений состояния в соответствии с решетчатой структурой декодирующего устройства и каждая ячейка в первом столбце принимает множество значений состояния, определенных в соответствии с решетчатой структурой кодера, заключающийся в том, что вычисляют значение метрики ветви для каждой ветви в каждом состоянии решетки, определенной кодером, выдают сигналы выбора пути для выбора пути с использованием вычисленных значений метрики ветви и значения метрики непосредственно предшествующего пути, выбирают в одной из множества ячеек одно из принятых значений состояния в ответ на сигнал выбора для сохранения выбранного значения состояния и выдают значение МП состояния в ячейках последнего столбца.11. Способ по п.10, отличающийся тем, что каждая ячейка содержит mx1 мультиплексор.12. Способ по п.10, отличающийся тем, что значения состояния, хранимые в ячейках одного и того же столбца, становятся одинаковыми после истечения заданного времени.13. Способ по п.10, отличающийся тем, что если значения состояния, выданные из ячеек последнего столбца, различаются, в качестве значения МП состояния выбирается значение состояния, имеющее большее число.