УСТРОЙСТВО ДЕКОДИРОВАНИЯ И УСТРОЙСТВО ПРИЕМА
DEVICE FOR DECODING AND DEVICE FOR RECEPTION

Это изобретение относится к устройству декодирования для исправления блочных ошибок, в котором последовательность принятых данных делится на множество блоков, каждый заданной длины, и последовательность избыточности прикрепляется от блока к блоку, и устройству приема, включающему в себя устройство декодирования. Более точно, оно относится к устройству декодирования для кодов с контролем четности низкой плотности (LDPC) и устройству приема, включающему в себя устройство декодирования.
УРОВЕНЬ ТЕХНИКИ
В системах спутниковой связи или системах мобильной связи, технологии кодирования с исправлением ошибок, имеющие большое усиление при кодировании, вводятся, чтобы удовлетворять требованиям к конфигурациям систем, таким как снижение потребляемой мощности или размера антенны. Код с контролем четности низкой плотности известен как код с исправлением ошибок, имеющий очень высокое усиление при кодировании, и перенимается все больше и больше для использования в многообразии систем связи и устройствах записи, таких как устройства магнитной записи.
Код с контролем четности низкой плотности не определяет единственную систему кодирования с исправлением ошибок, но обозначает в совокупности систему кода с исправлением ошибок, наделенную отличительным признаком по той причине, что проверочная матрица является разреженной, то есть элементы проверочной матрицы, по большей части, являются 0, с количеством элементов 1, являющимся крайне малым.
Код с контролем четности низкой плотности наделен отличительным признаком согласно тому факту, что посредством использования системы итеративного декодирования, такой как алгоритм суммы произведений или алгоритм суммы минимумов, с выбором разреженной проверочной матрицы, может конструироваться система кодирования с исправлением ошибок, которая имеет крайне большое усиление при кодировании, близкое к теоретическому пределу (например, смотрите непатентную публикацию 1 и непатентную публикацию 2).
Устройство декодирования для кода с контролем четности низкой плотности выполняет операцию обновления сообщения переменной для проверки процессором узла переменной и операцию обновления сообщения проверки для переменной процессором узла проверки, в чередовании друг с другом. После обновления каждого сообщения заданное количество раз оцененный результат данных передачи получается из сообщения проверки для переменной и принятых данных (например, смотрите непатентную публикацию 2 и непатентную публикацию 3).
Непатентная публикация 1: Robert G. Gallager, 'Low Density Parity Check Codes', United States, MIT Press, 1963, pp.39-56 (Роберт Ж. Галлагер, «Коды с контролем четности низкой плотности», Соединенные Штаты, Издательство МТИ, 1963, стр. 39-56).
Непатентная публикация 2: David J.C. MacKay, 'Good Error-Correcting Codes Based on Very Sparse Matrices', United States, IEEE Transactions on formation Theory, Vol.45, No.2, March 1999, p399-431 (Дэвид Дж.К. Маккей, «Коды с хорошим исправлением ошибок, основанные на сильно разреженных матрицах», Соединенные Штаты, Протоколы IEEE по Теории построения, том 45, №2, Март 1999 г., стр. 399-431).
Непатентная публикация 3: Jinghu Chen and Marc P.C. Fossorier, 'Near Optimum Universal Belief Propagation Based Decoding of Low-Density Parity Check Codes', United States, IEEE Transactions on Communications, Vol.50, No.3, March 2002, pp.406-414 (Джингху Чен и Марк П.К. Фоссориер, «Основанное на близком к оптимальному по всеобщему мнению распространению декодирование кодов с контролем четности низкой плотности», Соединенные Штаты, Протоколы IEEE по связи), том 50, № 3, Март 2002 г., стр. 406-414).
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
ПРОБЛЕМЫ, КОТОРЫЕ ДОЛЖНЫ БЫТЬ РЕШЕНЫ ИЗОБРЕТЕНИЕМ
Среди технических проблем системы декодирования кодов с контролем четности низкой плотности есть проблемы, такие, что необходимо много оперативных запоминающих устройств (ОЗУ, RAM), и такая, что скорость доступа к ОЗУ накладывает ограничения на скорость обработки декодирования в целом.
Более точно, обработка декодирования кодов с контролем четности низкой плотности включает в себя обновление сообщения двумя разновидностями устройств обработки и обязательна память для временного хранения сообщений. Есть некоторое количество сообщений, пропорциональное количеству '1'-иц в проверочной матрице, и, если эти сообщения удерживаются в ОЗУ в качестве устройства хранения данных, необходимы многочисленные ОЗУ, а отсюда провоцируется проблема, что скорость доступа к ОЗУ накладывает ограничения на скорость обработки декодирования.
Также есть проблема, что, если количество ОЗУ должно быть уменьшено, ограничения накладываются на количество сообщений, к которым может одновременно осуществляться доступ. Отсюда возникает необходимость, что регламенту обновления сообщений или формированию адресов необходимо тонко регулироваться, таким образом усложняя строение устройства.
Соответственно, цель настоящего изобретения состоит в том, чтобы предложить устройство декодирования упрощенной конструкции и небольшого размера, допускающее быстрое декодирование кодов с контролем четности низкой плотности, и устройство приема, включающее в себя устройство декодирования.
СРЕДСТВО ДЛЯ РЕШЕНИЯ ПРОБЛЕМ
Согласно настоящему изобретению предложено устройство декодирования для декодирования псевдоциклических кодов с контролем четности низкой плотности при кодировании с исправлением ошибок и для вывода оцененной последовательности битов передачи в качестве результата декодирования, которое содержит средство формирования сообщения переменной для проверки, средство формирования сообщения проверки для переменной и средство обработки нормализации. Средство формирования сообщения переменной для проверки включает в себя множество регистров сдвига с обратными связями предопределенного количества ступеней, включающих в себя множество регистров, средство формирования сообщения переменной для проверки принимает последовательность принятых данных, формирует и выводит сообщение переменной для проверки и оцененную последовательность битов передачи. Сообщение переменной для проверки является данными, заключающими в себе сумму отношения логарифмического правдоподобия и априорного значения. Средство формирования сообщения проверки для переменной включает в себя множество регистров сдвига с обратными связями заданного количества ступеней, включающих в себя множество регистров. Средство формирования сообщения проверки для переменной выводит, по приему сообщения переменной для проверки, выведенного из средства формирования сообщения переменной для проверки, сообщение проверки для переменной, включая данные, сформированные в ответ на принятое сообщение переменной для проверки. Средство обработки нормализации для перемножения заданных данных, включенных в сообщение проверки для переменной, выведенное средством формирования сообщения проверки для переменной, с заданной константой и для вывода результирующего произведения в средство формирования сообщения переменной для проверки. Средство формирования сообщения переменной для проверки включает в себя средство обработки переменной для проверки для суммирования данных, соответствующих выходу средства формирования сообщения проверки для переменной в заданные данные из данных, удерживаемых в регистрах из числа регистров сдвига с обратными связями, включенных в средство формирования сообщения переменной для проверки, и для сохранения результирующей суммы в регистре следующей ступени. Средство обработки переменной для проверки выводит, при заданной временной привязке, оцененную последовательность битов передачи и сообщение переменной для проверки, включающее в себя данные, удерживаемые в регистре. Средство формирования сообщения проверки для переменной включает в себя средство обработки проверки для переменной для выбора двух данных из данных, удерживаемых регистрами из числа регистров сдвига с обратными связями средства формирования сообщения проверки для переменной, а также данных наименьшего значения и данных второго наименьшего значения из данных, выведенных средством обработки переменной для проверки, для сохранения данных, выбранных в регистре следующей ступени, и для вывода данных, удерживаемых в регистре, при заданной временной привязке, в качестве сообщения проверки для переменной. Средство формирования сообщения переменной для проверки скомпоновано между регистрами из числа регистров сдвига с обратными связями средства формирования сообщения проверки для переменной. Средство формирования сообщения проверки для переменной скомпоновано между регистрами из числа регистров сдвига с обратными связями средства формирования сообщения проверки для переменной.
Средство формирования сообщения переменной для проверки может включать в себя первый счетчик тактовых импульсов, синхронизированный с рабочим тактовым сигналом регистра сдвига с обратными связями средства формирования сообщения переменной для проверки. Средство формирования сообщения проверки для переменной включает в себя второй счетчик тактовых импульсов, синхронизированный с рабочим тактовым сигналом регистра сдвига с обратными связями средства формирования сообщения проверки для переменной. Средство обработки переменной для проверки выбирает в ответ на значение счета первого счетчика тактовых импульсов данные, которые должны суммироваться, с частью данных, удерживаемых в регистре средства формирования сообщения переменной для проверки. Регистр средства формирования сообщения проверки для переменной удерживает значение счета второго счетчика тактовых импульсов. Средство обработки проверки для переменной выводит, когда данные, соответствующие выходу средства формирования сообщения переменной для проверки, стали наименьшим значением, числовое значение, соответствующее значению счета второго счетчика тактовых импульсов, удерживаемому регистром, и заставляет выходное значение удерживаться в регистре следующей ступени.
Средство формирования сообщения переменной для проверки может включать в себя первый счетчик тактовых импульсов, синхронизированный с рабочим тактовым сигналом регистра сдвига с обратными связями средства формирования сообщения переменной для проверки. Средство формирования сообщения проверки для переменной включает в себя второй счетчик тактовых импульсов, синхронизированный с рабочим тактовым сигналом регистра сдвига с обратными связями средства формирования сообщения проверки для переменной. Средство обработки переменной для проверки выбирает, в ответ на значение счета первого счетчика тактовых импульсов и числовое значение, назначенное регистру из числа регистров сдвига с обратными связями средства формирования сообщения переменной для проверки, данные, которые должны суммироваться, с частью данных, удерживаемых в регистре средства формирования сообщения переменной для проверки. Регистр средства формирования сообщения проверки для переменной удерживает значение счета второго счетчика тактовых импульсов. Средство обработки проверки для переменной выводит, когда данные, соответствующие выходу средства формирования сообщения переменной для проверки, стали наименьшим значением, набор значения счета второго счетчика тактовых импульсов, удерживаемый регистром, и числовое значение, назначенное регистру средства формирования сообщения переменной для проверки.
Средство формирования сообщения переменной для проверки и средство формирования сообщения проверки для переменной могут повторять формирование и вывод сообщения переменной для проверки, а также формирование и вывод сообщения проверки для переменной заданное количество раз. Средство формирования сообщения переменной для проверки выводит оцененную последовательность битов передачи после повторения формирования сообщения переменной для проверки заданное количество раз.
Средство формирования сообщения переменной для проверки может включать в себя такое же количество регистров и средств обработки проверки для переменной, как размер циклической матрицы, составляющей проверочную матрицу псевдоциклических кодов с контролем четности низкой плотности. Предпочтительно средство формирования сообщения переменной для проверки включает в себя такое же количество регистров и средств обработки проверки для переменной, как размер циклической матрицы, составляющей проверочную матрицу псевдоциклических кодов с контролем четности низкой плотности. Средство формирования сообщения проверки для переменной включает в себя такое же количество регистров и средств обработки проверки для переменной, как размер циклической матрицы, составляющей проверочную матрицу псевдоциклических кодов с контролем четности низкой плотности.
Согласно настоящему изобретению предложено устройство приема, включающее в себя устройство декодирования для декодирования псевдоциклических кодов с контролем четности низкой плотности при кодировании с исправлением ошибок и для вывода оцененной последовательности битов передачи, которое содержит демодулятор для демодуляции и вывода принимаемой информации, и устройство преобразования управляющих данных синхронизации для преобразования выходных данных демодулятора во входные данные вида, приведенного в соответствие устройству декодирования. Устройство декодирования включает в себя средство формирования сообщения переменной для проверки, в свою очередь, включающее в себя множество регистров сдвига с обратными связями предопределенного количества ступеней, включающих в себя множество регистров. Средство формирования сообщения переменной для проверки принимает последовательность принятых данных, формируя и выводя сообщение переменной для проверки и оцененную последовательность битов передачи. Сообщение переменной для проверки является данными, содержащими сумму отношения логарифмического правдоподобия и априорного значения. Устройство декодирования также включает в себя средство формирования сообщения проверки для переменной, в свою очередь, включающее в себя множество регистров сдвига с обратными связями заданного количества ступеней, включающих в себя множество регистров. Средство формирования сообщения проверки для переменной выводит, по приему сообщения переменной для проверки, выведенного из средства формирования сообщения переменной для проверки, сообщение проверки для переменной, включая данные, сформированные в ответ на принятое сообщение переменной для проверки. Устройство декодирования также включает в себя средство обработки нормализации для перемножения заданных данных, включенных в сообщение проверки для переменной, выведенное средством формирования сообщения проверки для переменной, с заданной константой и для вывода результирующего произведения в средство формирования сообщения переменной для проверки. Средство формирования сообщения переменной для проверки включает в себя средство обработки переменной для проверки для суммирования данных, соответствующих выходу средства формирования сообщения проверки для переменной, с заданными данными из числа данных, удерживаемых в регистрах из числа регистров сдвига с обратными связями, включенных в средство формирования сообщения переменной для проверки, и для сохранения результирующей суммы в регистре следующей ступени. Средство обработки переменной для проверки выводит, при заданной временной привязке, оцененную последовательность битов передачи и сообщение переменной для проверки, включающее в себя данные, удерживаемые в регистре. Средство формирования сообщения проверки для переменной включает в себя средство обработки проверки для переменной для выбора двух данных из данных, удерживаемых регистрами из числа регистров сдвига с обратными связями средства формирования сообщения проверки для переменной, а также данных наименьшего значения и данных второго наименьшего значения из данных, выведенных средством обработки переменной для проверки, для сохранения данных, выбранных в регистре следующей ступени и для вывода данных, удерживаемых в регистре, при заданной временной привязке, в качестве сообщения проверки для переменной. Средство формирования сообщения переменной для проверки скомпоновано между регистрами из числа регистров сдвига с обратными связями средства формирования сообщения проверки для переменной. Средство формирования сообщения проверки для переменной скомпоновано между регистрами из числа регистров сдвига с обратными связями средства формирования сообщения проверки для переменной.
ПОЛЕЗНЫЕ РЕЗУЛЬТАТЫ ИЗОБРЕТЕНИЯ
Согласно настоящему изобретению, в котором устройство хранения данных для временного хранения сообщений (ОЗУ) не используется, возможно осуществлять декодирование кодов с контролем четности низкой плотности на высокой скорости. В дополнение, формирование и управление адресом ОЗУ являются необязательными, тем самым упрощая управление и конфигурацию.
Если арифметический операционный узел проверки для переменной сконфигурирован для вывода числового значения, соответствующего значению счета второго счетчика тактовых импульсов, удерживаемому регистром, когда данные, соответствующие выходу средства формирования переменной для проверки, стали наименьшим значением, устройство декодирования во всей своей полноте может быть уменьшено в размерах.
К тому же, если арифметический операционный узел проверки для переменной сконфигурирован для вывода набора значения счета второго счетчика тактовых импульсов, удерживаемого регистром, и числового значения, назначенного регистру средства формирования переменной для проверки, когда данные, соответствующие выходу средства формирования переменной для проверки, стали наименьшим значением, возможно формировать сообщение проверки для переменной с высокой точностью.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Фиг.1 - структурная схема, показывающая пример конфигурации первого примерного варианта осуществления устройства декодирования согласно настоящему изобретению.
Фиг.2 - структурная схема, показывающая пример конфигурации формирователя сообщения переменной для проверки.
Фиг.3 - структурная схема, показывающая пример конфигурации блока регистров переменной для проверки.
Фиг.4 - структурная схема, показывающая пример конфигурации блока узлов обработки переменной для проверки.
Фиг.5 - структурная схема, показывающая пример конфигурации формирователя сообщения проверки для переменной.
Фиг.6 - структурная схема, показывающая пример конфигурации блока регистров проверки для переменной.
Фиг.7 - структурная схема, показывающая пример конфигурации блока узлов обработки проверки для переменной.
Фиг.8 - схематический вид, показывающий работу устройства декодирования в целом.
Фиг.9 - структурная схема, показывающая пример конфигурации устройства декодирования для кодов с контролем четности низкой плотности, использующей ОЗУ.
Фиг.10 - структурная схема, показывающая пример конфигурации упрощенного блока узлов обработки переменной для проверки.
Фиг.11 - структурная схема, показывающая пример конфигурации упрощенного блока узлов обработки проверки для переменной.
Фиг.12 - структурная схема, показывающая пример конфигурации устройства (хранения) передачи данных, использующего устройство декодирования согласно настоящему изобретению.
УСЛОВНЫЕ ОБОЗНАЧЕНИЯ
11 формирователь сообщения переменной для проверки
12 формирователь сообщения проверки для переменной
13 узел обработки нормализации
21 блок регистров переменной для проверки
22, 52 блоки счетчиков
23, 41, 101 сумматоры
31, 61 регистры
32 блок узлов обработки переменной для проверки
33, 63 переключатели соединений
34, 64 выходные переключатели
42, 102 инверторы плюса или минуса
43, 73, 74, 113 селекторы
44, 71, 72, 111, 112 компараторы
45, 75, 103, 114 логические элементы исключающего ИЛИ
51 блок узлов обработки проверки для переменной
81 процессор узла переменной
82 контроллер формирователя адреса
83 процессор узла проверки
84 блок памяти сообщений
121 устройство передачи данных
122 устройство кодирования
123, 127 преобразователь управляющих данных синхронизации
124 узел модуляции
125 устройство приема данных
126 демодулятор
128 устройство декодирования
ПРЕДПОЧТИТЕЛЬНЫЕ ВАРИАНТЫ ДЛЯ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ
Первый примерный вариант осуществления
Первый примерный вариант осуществления устройства декодирования по настоящему изобретению далее описан со ссылкой на чертежи. Фиг.1 - структурная схема, показывающая первый примерный вариант осуществления устройства декодирования согласно настоящему изобретению.
Устройство декодирования согласно настоящему изобретению включает в себя формирователь 11 сообщения переменной для проверки (средство формирования сообщения переменной для проверки), формирователь 12 сообщения проверки для переменной (средство формирования сообщения проверки для переменной) и узел 13 обработки нормализации (средство обработки нормализации).
Последовательность принятых данных подается в формирователь 11 сообщения переменной для проверки из сети связи, к которой присоединено устройство декодирования. Поскольку, вообще, бывают ошибки в принятых данных, например, вследствие шума, устройство декодирования оценивает последовательность переданных битов и выводит оцененную последовательность переданных битов.
Псевдоциклические коды с контролем четности низкой плотности наделены отличительным признаком благодаря виду проверочной матрицы. Проверочная матрица псевдоциклических кодов с контролем четности низкой плотности является блочной матрицей axa, содержащей, в качестве элемента, циклическую матрицу axa, как показано в равенстве (1):
[Равенство 1]
где a, m и n обозначают положительные целые числа.
Обращено внимание, что Hi, j по равенству (1) обозначает циклическую матрицу axa, показанную следующим равенством (2):
[Равенство 2]
где i обозначает целое число от 0 до m-1, а j обозначает целое число от 0 до n-1.
С циклической матрицей, вектор-строка второй строки получается при сдвиге вектор-строки первой строки влево на один бит и так далее, так что вектор-строка k-й (где k - целое число, не меньшее чем 2, и не большее чем 2) строки получается при сдвиге вектора-строки 1-й строки на k-1 битов влево.
Далее описано устройство декодирования псевдоциклических кодов с контролем четности низкой плотности, проверочная матрица которого является матрицей по равенству (1).
Последовательность данных, принятых из сети связи, подается в формирователь 11 сообщения переменной для проверки. Выходные данные формирователя 12 сообщения проверки для переменной также подаются в формирователь сообщения переменной для проверки через узел 13 обработки нормализации. Выходные данные формирователя 12 сообщения проверки для переменной включают в себя последовательности данных, классифицированных на такое же количество видов, как количество m блоков строки проверочной матрицы. Выходные данные формирователя 12 сообщения проверки для переменной будут описаны позже.
n
Фиг.2 - структурная схема, показывающая пример конфигурации формирователя 11 сообщения переменной для проверки. Формирователь 11 сообщения переменной для проверки включает в себя некоторое количество блоков 21 регистров переменной для проверки, равное общему количеству  блоков столбца проверочной матрицы, сумматоры 23 и блок 22 счетчика (первый счетчик тактовых импульсов), который является счетчиком, синхронизированным с тактовым сигналом регистра 31, предусмотренного в блоке 21 регистров переменной для проверки.
n
n
Каждый блок 21 регистров переменной для проверки снабжается выходными данными формирователя 12 сообщения проверки для переменной через узел 13 обработки нормализации. Выходные данные каждого блока 21 регистров переменной для проверки суммируются в сумматоре 21 с частью последовательности принятых данных, соответствующих блоку столбца проверочной матрицы, ассоциативно связанному с блоком 21 регистров переменной для проверки. Результат сложения становится выходными данными формирователя 11 сообщения переменной для проверки. Количество блоков 21 регистров переменной для проверки является таким же, как общее количество  блоков столбца проверочной матрицы, а выходными данными формирователя 11 сообщения переменной для проверки являются  последовательностей, соответствующих выходным данным блоков 21 регистров переменной для проверки.
a
Фиг.3 - структурная схема, показывающая пример конфигурации блока 21 регистров переменной для проверки. Блок 21 регистров переменной для проверки включает в себя такое же количество  регистров 31, как размер циклической матрицы, составляющей проверочную матрицу, и блок 32 узлов обработки переменной для проверки (средство обработки переменной для проверки), скомпонованный между регистрами 31. Блок 21 регистров переменной для проверки также включает в себя переключатели 33 соединений и выходной переключатель 34. Обращено внимание, что размер циклической матрицы означает количество строк или количество столбцов циклической матрицы. Циклическая матрица является квадратной матрицей, и отсюда ее количества строк и столбцов равны друг другу.
Регистры 31 соединены последовательно один с другим через блоки 32 узлов обработки переменной для проверки. Выходной переключатель 34 присоединен к регистру 31 последней ступени. Выходной переключатель 34 переключается, так что выход регистра 31 последней ступени подается обратно на вход регистра 31 начальной ступени и так что выходные данные регистра последней ступени подаются в сумматор 23 после окончания заданного количества раз операций обратной связи.
Между тем, блок регистров, в котором выходные данные регистров последовательно подаются в регистры стороны выхода, а выходные данные регистра последней ступени подаются обратно в регистр начальной ступени, называется сдвиговым регистром с обратными связями.
m
m
a
Каждый блок 21 регистров переменной для проверки снабжается в качестве входных данных  последовательностями данных, причем количество  является таким же, как количество блоков строки проверочной матрицы. Когда были введены все данные, выходной переключатель 34 переключается, чтобы последовательно выводить часть данных, удерживаемых  регистрами 31.
m
a
0
1
a-1
(i)
(i)
(i)
Переключатели 33 соединений определяют, должны или нет входные данные блока 21 регистров переменной для проверки подаваться в блоки 32 узлов обработки переменной для проверки  последовательностями h , h ,..., h  битов, каждая состоящая из  битов, где i обозначает целое число от 0 до m-1. То есть переключатели 33 соединений определяют, должны или нет входные данные в блок 21 регистров переменной для проверки подаваться в блоки 32 узлов обработки переменной для проверки, в зависимости от того, присоединен или нет входной конец непоказанного блока 21 регистров переменной для проверки к каждому блоку 32 узлов обработки переменной для проверки.
k
k
k
k
0
1
a-1
(i)
(i)
(i)
(i)
(i)
(i)
(i)
m
a
Более подробно, если h  является 1, k является целым числом от 0 до a-1, часть, обозначенная h  на фиг.3, присоединена, тогда как, если h  является 0, часть, обозначенная h , не присоединена. Блок 21 регистров переменной для проверки включает в себя такое же количество блоков 32 узлов обработки переменной для проверки, как количество соединений. Способ выбора этих  последовательностей h , h ,..., h  битов, каждая состоящая из  битов, где i обозначает целое число от 0 до m-1, будет описан позже.
Фиг.4 - структурная схема, показывающая пример конфигурации блока 32 узлов обработки переменной для проверки. Узел обработки переменной для проверки включает в себя сумматор 41, компаратор 44, селектор 43, инвертор 42 плюса и минуса и логический элемент 45 исключающего ИЛИ. Работа блока 32 узлов обработки переменной для проверки будет описана позже.
m
Фиг.5 - структурная схема, показывающая пример конфигурации формирователя 12 сообщения проверки для переменной. Этот формирователь 12 сообщения проверки для переменной включает в себя некоторое количество блоков 51 регистров проверки для переменной, которое является таким же, как общее количество  блоков строки проверочной матрицы, и блок 52 счетчиков (второй счетчик тактовых импульсов), который является счетчиком, синхронизированным с тактовым сигналом регистра 61, включенного в блоки 51 регистров проверки для переменной.
Входные данные каждого блока 51 регистров проверки для переменной являются выходными данными формирователя 11 сообщения переменной для проверки. То есть выходные данные каждого блока 21 регистров проверки для переменной формирователя 11 сообщения переменной для проверки подаются через сумматор 23 в формирователь 11 сообщения переменной для проверки.
m
Количество блоков 51 регистров проверки для переменной равно количеству  блоков строки проверочной матрицы. Выходные данные формирователя 11 сообщения переменной для проверки являются последовательностями, соответствующими выходным данным блоков 51 регистров проверки для переменной.
a
a
Фиг.6 - структурная схема, показывающая пример конфигурации блоков 51 регистров проверки для переменной. Эти блоки 51 регистров проверки для переменной включают в себя  регистров 61, множество блоков 62 узлов обработки проверки для переменной (средств обработки проверки для переменной), множество переключателей 63 соединений и выходной переключатель 64. Количество  регистров равно размеру циклических матриц, составляющих проверочную матрицу, и блоки узлов обработки проверки для переменной скомпонованы между соседними регистрами 61.
Регистры 61 соединены последовательно один с другим через блоки 62 узлов обработки проверки для переменной. Выходной переключатель 64 присоединен к регистру 61 последней ступени. Выходной переключатель 64 переключается, так что выход регистра 61 последней ступени подается обратно на вход регистра 61 начальной ступени и так что выходные данные регистра последней ступени подаются в узел 13 обработки нормализации после окончания заданного количества раз операций обратной связи.
m
m
a
Каждый блок 51 регистров проверки для переменной снабжается  последовательностями, причем количество  является таким же, как количество блоков строки проверочной матрицы. Когда были поданы все данные, выходной переключатель 64 переключается, чтобы последовательно выводить часть данных, удерживаемых  регистрами 61.
n
a
0
1
a-1
(j)
(j)
(j)
Переключатели 63 соединений определяют, должны или нет входные данные блока 51 регистров переменной для проверки подаваться в блоки 62 узлов обработки проверки для переменной  последовательностями g , g ,..., g  битов, каждая состоящая из  битов, где j обозначает целое число от 0 до n-1. То есть переключатели 63 соединений определяют, должны или нет входные данные в блок 51 регистров проверки для переменной подаваться в блоки 62 узлов обработки проверки для переменной, в зависимости от того, присоединен или нет входной конец не показанных блоков 51 регистров проверки для переменной к каждому блоку 62 узлов обработки проверки для переменной.
k
k
k
k
0
1
a-1
(j)
(j)
(j)
(j)
(j)
(j)
(j)
m
a
Более подробно, если g  является 1, k является целым числом от 0 до a-1, часть, обозначенная g  на фиг.3, присоединена, тогда как если g  является 0, часть, обозначенная g , не присоединена. Блок 62 узлов обработки проверки для переменной включает в себя такое же количество блоков узлов обработки проверки для переменной, как количество соединений. Способ выбора этих  последовательностей g , g ,..., g  битов, каждая состоящая из  битов, где j обозначает целое число от 0 до n-1, будет описан позже.
Фиг.7 - структурная схема, показывающая пример конфигурации блока 62 узлов обработки проверки для переменной. Блок 62 узлов обработки проверки для переменной включает в себя компараторы 71, 72, селекторы 73, 74 и логический элемент 75 ИСКЛЮЧАЮЩЕЕ ИЛИ. Работа блока 62 узлов обработки проверки для переменной будет описана позже.
a
С устройством декодирования по настоящему изобретению, выходные данные формирователя 11 сообщения переменной для проверки подаются в формирователь 12 сообщения проверки для переменной, а выходные данные формирователя 12 сообщения проверки для переменной подаются в формирователь 11 сообщения переменной для проверки. Эта последовательность операций повторяется заданное количество раз, и последовательность битов, полученная в жестком решении выходных данных формирователя 11 сообщения переменной для проверки, подается в качестве выходных данных устройства декодирования. 2xa тактовых импульсов,  является размером циклической матрицы, составляющей проверочную матрицу, необходимы для каждой итеративной обработки. Обработка декодированием подходит к концу с количеством тактовых импульсов, соответствующим количеству раз итеративных операций, равным 2xa.
m
a
Далее описан выбор -битных последовательностей, который определяет соединение блоков 21 регистров переменной для проверки, описанных выше.
n
m
m
a
0,j
i,j
m-1,j
0
1
a-1
0
1
a-1
0
1
a-1
0
1
a-1
(0,j)
(0,j)
(0,j)
(1,j)
(1,j)
(1,j)
(m-1,j)
(m-1,j)
(m-1,j)
(i)
(i)
(i)
Как упомянуто выше, количество блоков 21 регистров переменной для проверки является таким же, как общее количество  блоков столбца проверочной матрицы. Блоки 21 регистров переменной для проверки соответствуют блокам столбца проверочной матрицы. Как показано в равенствах (1) и (2), j-й блок столбца, j является целым числом от 0 до n-1, составлен из  циклических матриц axa, H, H,..., H, с вектор-строками этих циклических матриц, совпадающими с циклическим сдвигом (f , f ,..., f ), (f , f ,..., f ),..., (f , f ,..., f ) соответственно. -битных последовательностей h , h ,..., h , где i=0, 1,..., m-1, могут определяться с использованием вышеприведенных вектор-строк, по следующему равенству (3):
[Равенство 3]
n
k
(i,j)
Как описано выше, соединения в  блоках 21 регистров переменной для проверки зависят от блоков столбцов проверочной матрицы, с которыми ассоциативно связаны соединения. В последующем соединения и блоки регистров переменной для проверки отличаются друг от друга и соединения, ассоциативно связанные с j-м блоком столбца проверочной матрицы, j является целым числом от 0 до n-1, обозначены как h .
Далее описана информация (данные), удерживаемая и обновляемая в регистрах 31 в каждом блоке 21 регистров переменной для проверки. Информация, удерживаемая и обновляемая в регистрах 31, составлена из части сообщения и одного дополнительного бита. Часть сообщения является данными, соответствующими сообщению переменой для проверки (сообщению VC), а дополнительный один бит обозначает знак плюс или минус данных части сообщения, рассчитанной блоком 32 узлов обработки переменной для проверки в непосредственно предыдущей итеративной обработке. Эти данные будут подробно описаны позже.
n
a
m
Далее будет описан выбор -битных последовательностей, определяющий соединения блока 51 регистров проверки для переменной, описанные выше. Количество блоков 51 регистров проверки для переменной равно общему количеству  блоков строки проверочной матрицы, с блоками 51 регистров проверки для переменной, стыкующимися с блоками строки проверочной матрицы.
n
0,j
i,j
m-1,j
0
1
a-1
0
1
a-1
0
1
a-1
(i,0)
(i,0)
(i,0)
(i,1)
(i,1)
(i,1)
(i,n-1)
(i,n-1)
(i,n-1)
Как показано в равенствах (1) и (2), i-й блок строки, где i обозначает целое число от 0 до m-1, составлен из  циклических матриц axa, H, H,..., H, с вектор-строками этих циклических матриц, совпадающими с циклическим сдвигом (f , f ,..., f ), (f , f ,..., f ),..., (f , f ,..., f ) соответственно.
n
a
0
1
a-1
(j)
(j)
(j)
-битных последовательностей g , g ,..., g , где j=0, 1,..., m-1, могут определяться с использованием вышеприведенных вектор-строк, по следующему равенству (4):
[Равенство 4]
n
k
(i,j)
Как описано выше, соединения в  блоках 51 регистров проверки для переменной зависят от блоков столбцов проверочной матрицы, с которыми ассоциативно связаны соединения. В последующем соединения и блоки регистров переменной для проверки отличаются друг от друга и соединения, ассоциативно связанные с i-м блоком столбца проверочной матрицы, i является целым числом от 0 до m-1, обозначены как g .
Далее описана информация (данные), удерживаемая и обновляемая в регистрах 61 в каждом блоке 51 регистров переменной для проверки. Информация, удерживаемая и обновляемая в регистрах 61, составлена из части сообщения, значения счетчика тактовых импульсов и одного дополнительного бита. Часть сообщения является данными, соответствующими сообщению проверки для переменной (сообщению CV).
Дополнительный один бит, рассчитанный формирователем 11 сообщения переменной для проверки, является синдромом для результата жесткого решения, квантованного в одном бите, по сообщению, рассчитанному формирователем 11 сообщения переменной для проверки и подаваемому в формирователь 12 сообщения проверки для переменной. Если эти битовые значения все являются нулевыми, результат жесткого решения по сообщению, рассчитанный формирователем 11 сообщения переменной для проверки, представляет кодовое слово и является оцененной последовательностью битов передачи, выводимой из устройства декодирования. Вышеприведенные данные будут подробно описаны позже.
Далее будет описана работа первого примерного варианта осуществления настоящего изобретения. В начале будут описаны входные данные и выходные данные формирователя 11 сообщения переменной для проверки, и входные данные и выходные данные формирователя 12 сообщения проверки для переменной. Выходные данные формирователя 12 сообщения проверки для переменной подаются в формирователь 11 сообщения переменной для проверки через узел 13 обработки нормализации.
t,1
t,2
2
t,1
t,2
2
(s)
(s)
(s)
(s)
Выходные данные формирователя 12 сообщения проверки для переменной грубо классифицируются на четыре вида данных, помеченных L , L , P(s,t) и μ(s,t), где s и t обозначают целое число от 0 до m-1 и целое число от 0 до a-1 соответственно. L , L  являются данными, эквивалентными сообщению проверки для переменной, а P(s,t) является однобитными данными, представляющими произведение результата жесткого решения по входным данным формирователя 12 сообщения проверки для переменной (выходным данным формирователя 11 сообщения переменной для проверки), например самым старшим двоичным разрядом, и проверочной матрицы по равенству (1).
μ(s,t) используется по-разному в зависимости от точности расчета. Конкретно, если требуется высокая точность расчета, μ(s,t) является данными, представляющими набор двух целых чисел, а если достаточна более низкая точность расчета, μ(s,t) является данными, представляющими одиночное целое число. Если достаточна еще более низкая точность расчета, данные μ(s,t) не используются. С уменьшением точности расчета объем данных μ(s,t) становится меньшим, так что уменьшается размер устройства.
Далее описан случай максимальной точности расчета, при которой μ(s,t) обозначает набор из двух целых чисел, а μ(s,t) будет описано позже.
t,1
t,2
2
2
t,1
t,2
t,1
t,2
(s)
(s)
(s)
(s)
(s)
(s)
Выходные данные L , L , P(s,t) и μ(s,t) из формирователя 12 сообщения проверки для переменной подаются в узел 13 обработки нормализации. Что касается P(s,t) и μ(s,t), узел 13 обработки нормализации выводит такие же данные, как входные данные и, что касается L , L , он выводит входные данные, умноженные на заданную константу α, то есть αL  и αL .
t,1
t,2
2
t,1
t,2
2
(s)
(s)
(s)
(s)
Отсюда выходные данные L , L , P(s,t) и μ(s,t) из формирователя 12 сообщения проверки для переменной не подаются непосредственно в формирователь сообщения переменной для проверки, но αL , αL , P(s,t) и μ(s,t) подаются в формирователь 11 сообщения переменной для проверки.
t,1
t,2
2
(s)
(s)
В описании, которое следует, это представление с умножением на константу α не используется, чтобы предотвратить неправильное употребление символов. То есть входные данные в формирователь 11 сообщения переменной для проверки представлены L , L , P(s,t) и μ(s,t), которые стоят за выходными данными формирователя 12 сообщения проверки для переменной.
Входные данные в формирователь 11 сообщения переменной для проверки являются выходными данными формирователя 12 сообщения проверки для переменной и выходными данными маршрута Fi связи, где i обозначает целое число от 0 до na-1.
m
t,1
t,2
2
(s)
(s)
Формирователь 12 сообщения проверки для переменной включает в себя такое же количество блоков 51 регистров проверки для переменной, как общее количество  блоков строки проверочной матрицы (равенство 1). Входными данными в момент t времени s-х блоков 51 регистров проверки для переменной становятся L , L , P(s,t) и μ(s,t), где s обозначает целое число от 0 до m-1, а t обозначает целое число от 0 до a-1. Они являются данными, удерживаемыми регистрами 61 в блоках 51 регистров проверки для переменной во время вывода.
r
r
r
1
(l)
(l)
(l)
l,r
n
Выходные данные формирователя 11 сообщения переменной для проверки также подаются в формирователь 12 сообщения проверки для переменной. Эти входные данные обозначены как Z , где l обозначает целое число от 0 до n-1, а r обозначает целое число от 0 до a-1. Формирователь 11 сообщения переменной для проверки включает в себя такое же количество блоков 21 регистров переменной для проверки, как общее количество  блоков столбца проверочной матрицы (равенство 1). r-е выходные данные l-го блока 21 регистров переменной для проверки становятся Z , где l обозначает целое число от 0 до n-1, а r обозначает целое число от 0 до a-1. Z  и 1-битные данные P , которые пояснены позже, представляют данные, удерживаемые регистрами 31 в блоке 21 регистров переменной для проверки во время вывода.
t,1
t,2
2
i
r
(s)
(s)
(l)
Далее описана работа формирователя 11 сообщения переменной для проверки. В формирователь 11 сообщения переменной для проверки подаются L , L , P(s,t), μ(s,t) и выходные данные F тракта связи, где i, s и t обозначают целое число от 0 до na-1, целое число от 0 до m-1 и целое число от 0 до a-1 соответственно. Формирователь 11 сообщения переменной для проверки рассчитывает Z , где 1 и r указывают целое число от 0 до n-1 и целое число от 0 до a-1 соответственно, с использованием следующего равенства (5):
[Равенство 5]
1
r
1
r
(l, r)
(l)
(l, r)
(1)
В вышеприведенном равенстве (5) первый и второй члены представляют отношение логарифмического правдоподобия и априорное значение соответственно, а каждое P  является 1-битными данными, с самого начала сохраненными в регистрах 31 блока 21 регистров переменной для проверки в формирователе 11 сообщения переменной для проверки. Формирователь 11 сообщения переменной для проверки рассчитывает данные Z  сообщения переменной для проверки, где l и r указывают целое число от 0 до n-1 и целое число от 0 до a-1 соответственно, и обновляет P , используя рассчитанный таким образом Z , в соответствии со следующим равенством (6):
[Равенство 6]
1
r
(l, r)
(l)
То есть P  является 1-битными данными, соответствующими самому старшему двоичному разряду из Z . Последовательность этих данных (последовательность битов) выводится из устройства декодирования в качестве оцененной последовательности битов для передачи.
n
n
Далее описана работа блока 21 регистров переменной для проверки. Формирователь 11 сообщения переменной для проверки включает в себя такое же количество блоков 21 регистров переменной для проверки, как общее количество  блоков столбца проверочной матрицы (равенство 1). Каждый блок 21 регистров переменной для проверки включает в себя такое же количество  регистров 31, как размер циклической матрицы, составляющей проверочную матрицу.
r
r
r
(l)
(l)
(1)
Начальное состояние (значение в момент 0 времени) данных сообщения, удерживаемых в r-м регистре 31 в l-м блоке 21 регистров переменной для проверки, обозначено как Z (a), а данные сообщения в момент a-j времени обозначены как Z (j), где l, r и j обозначают целое число от 0 до n-1, целое число от 0 до a-1 и целое число от 0 до a-1 соответственно. С начальным состоянием Z (a)=0 данные сообщения в момент a-j времени могут рассчитываться по данным сообщения в момент a-j-1 времени в соответствии со следующим равенством (7):
[Равенство 7]
1
a
1
1
j
(l, r)
(1,r)
(l, r)
С начальным состоянием (значением в момент 0 времени) P  =P  обновляется символ P   в момент a-j времени в соответствии со следующим равенством (8).
[Равенство 8]
r
1
j
(1)
(l,r)
Данными, удерживаемыми в r-м регистре в момент времени a-j в первом блоке 21 регистров переменной для проверки формирователя 11 сообщения переменной для проверки, являются Z (j) и P  . Устройством, выполняющим обработку обновления этих данных в каждый момент времени в соответствии с равенствами (7) и (8), является блок 32 узлов обработки переменной для проверки, показанный на фиг.4.
,
1
2
2
1-in
in
1
2
2
1-in
in
Далее описан блок 32 узлов обработки переменной для проверки. Блок 32 узлов обработки переменной для проверки снабжается в качестве входных данных, cnt, μL, L, P, P и Z. Более точно, cnt и μ подаются на компаратор 44. L, L и выходные данные компаратора 44 подаются в селектор 43. P и P подаются на логический элемент 45 ИСКЛЮЧАЮЩЕЕ ИЛИ. Выходные данные селектора 43 и выходные данные логического элемента 45 ИСКЛЮЧАЮЩЕЕ ИЛИ подаются на инвертор 42 плюса и минуса. Выходные данные инвертора 42 плюса и минуса и Z подаются в сумматор 41.
1
2
1
2
in
Таким образом, селектор 43 выбирает L или L в ответ на результат сравнения cnt, который является значением счета тактовых импульсов, подаваемым в компаратор 44, и целым числом между 0 и n-1, назначенным регистру 31, и выбранные таким образом L или L прибавляются сумматором 41 к Z.
in
То есть значение, которое должно прибавляться к Z, выбирается в зависимости от значения счета тактовых импульсов и целого числа от 0 до n-1, назначенного регистру 31.
,
1
2
2
j,1
j,2
2
in
1-in
1-out
1-out
(s)
(s)
(i,j)
Отмечено, что μL, L и P соответствуют μ(i,j), L , L  и P  по равенству (7) соответственно и что cnt обозначает набор целого числа l между 0 и n-1, задаваемого из одного блока 21 регистров переменной для проверки в другой, и целого числа между 0 и (a-1), ассоциативно связанного со значением счета счетчика, синхронизированного с тактовым сигналом. С другой стороны, блок 32 узлов переменной для проверки выводит для выходных данных Z и P, Z и P, показанные в равенствах (9) и (10) соответственно.
[Равенство 9]
[Равенство 10]
1-out
1-out
in
1-in
Выведенные Z и P подаются через регистры 31 в качестве входных данных Z и P в следующий блок 32 узлов обработки переменной для проверки следующей ступени соответственно.
r
r
r
r
(0,1)
(1,1)
(2,1)
(m-1,1)
Обработка расчета, показанная равенством (7), может быть выражена размещением такого же количества блоков 32 узлов обработки переменной для проверки, как количество 1-иц в {h , h , h ,..., h }, между r-м регистром 31 и (r+1)-м регистром 31 в l-м блоке 21 регистров переменной для проверки. Отмечено, что l и r указывают целое число между 0 и n-1 и целое число между 0 и a-1 соответственно.
r
la+r
r
(l)
(l)
Согласно расчетам по равенствам (7) и (8) арифметическая сумма данных Z (0) сообщения, удерживаемых в r-м регистре 31 в l-м блоке 21 регистров переменной для проверки в момент времени a, и выходных данных в тракте F связи является совпадающей с Z  в равенстве (5), как показано следующим равенством (11):
[Равенство 11]
r
1
0
r
(l)
(l,r)
(1)
Данными, удерживаемыми в r-м регистре в момент времени a-j в первом блоке 21 регистров переменной для проверки формирователя 11 сообщения переменной для проверки, являются Z (0) и P  . Z (0) затем суммируется с использованием равенства (11), так что данные, удерживаемые в 0-м регистре 31 в каждом блоке 21 регистров переменной для проверки, выводятся в формирователь 12 сообщения проверки для переменной.
r
(l)
В то же самое время, когда выводятся данные, данные в (j+1)-м регистре 31 блока 21 регистров переменной для проверки сдвигаются в j-й регистр 31, где j обозначает целое число от 0 до a-2, с тем чтобы последовательно выводиться через 0-й регистр 31. Блок 21 регистров переменной для проверки инициализирует часть сообщения (a-1)-го регистра 31 и вводит 1-битные данные, выведенные по равенству (6) (a-1)-го регистра 31, наряду со вводом 1-битных данных, выведенных по равенству (6) из данных выходного сообщения Z . Регистры 31 инициализируются в момент времени, когда были выведены все данные.
a
Таким образом, для обработки ради формирования сообщения переменной для проверки  тактовых сигналов необходимы для каждой из операций обработки для ввода и обработки для вывода. Эти операции названы соответственно режимом обработки ввода и режимом вывода формирователя 11 сообщения переменной для проверки.
r
(l)
Посредством вышеприведенной обработки сообщение Z  переменной для проверки рассчитываются блоками 32 узлов обработки переменной для проверки с использованием ОЗУ. Блоки 32 узлов обработки переменной для проверки каждый, главным образом, состоят из сумматора 41 и предусмотрены между соседними регистрами 31.
t,1
t,2
2
(s)
(s)
(i,j)
Далее пояснена работа формирователя 12 сообщения проверки для переменной. Выходные данные формирователя 12 сообщения проверки для переменной вводятся в формирователь 11 сообщения переменной для проверки через узел 13 обработки нормализации. Как упомянуто выше, эти данные помечены L , L , а также P  и μ(i,j), где s и t обозначают целое число от 0 до m-1 и целое число от 0 до a-1 соответственно.
m
t,1
t,2
2
(s)
(s)
(i,j)
Формирователь 12 сообщения проверки для переменной включает в себя такое же количество блоков 51 регистров проверки для переменной, как общее количество  блоков столбца проверочной матрицы (равенство 1). (a-1-t)-е выходные данные в s-м блоке 51 регистров переменной для проверки становятся L , L , а также P  и μ(i,j), где s и t обозначают целое число от 0 до m-1 и целое число от 0 до a-1 соответственно. Таковые становятся данными, хранимыми в регистрах 61 в формирователе 12 сообщения проверки для переменной во время вывода.
r
t,1
t,2
(l)
(s)
(s)
Формирователь 12 сообщения проверки для переменной принимает выходные данные Z  формирователя 11 сообщения переменной для проверки, где l и r являются целым числом от 0 до n-1 и целым числом от 0 до a-1 соответственно, как упомянуто выше, и рассчитывает L  и L  по следующим равенствам (12) и (13).
[Равенство 12]
[Равенство 13]
t
t,1
t
t,2
t
(s)
(s)
(s)
(s)
(s)
В вышеприведенных равенствах W  обозначает набор, показанный следующим равенством (14). То есть L  обозначает элемент с наименьшим значением среди элементов набора W  равенства (14), а L  обозначает элемент со вторым наименьшим значением среди элементов набора W .
[Равенство 14]
j
j
2
(i)
(i)
Между тем, |Z | обозначает абсолютное значение Z . К тому же, P(s,t) рассчитывается по следующему равенству (15).
[Равенство 15]
1
j
r
r
(i,j)
i
(l)
l
В равенстве (15) каждый P  является 1-битными данными, представляющими плюс или минус Z , как показано в равенстве (6), приведенном выше. Этим способом выходные данные Z  формирователя 11 сообщения переменной для проверки подаются в формирователь 12 сообщения проверки для переменной. Однако выходные данные обрабатываются внутри формирователя 12 сообщения проверки для переменной в виде, разделенном на один бит (самый старший двоичный разряд), представляющий знак плюса или минуса у Z , другие битовые данные, представляющие абсолютное значение, иное, чем знак.
t
γ
t,1
γ
(s)
(i)
(s)
(λ)
С другой стороны, если элементом с наименьшим значением из элементов набора W  по равенству (14) является |Z |, то есть если L =|Z |, то μ(s,t) удовлетворяет следующему равенству (16):
[Равенство 16]
m
a
Далее пояснена работа блока 51 регистров сообщения проверки для переменной. Формирователь 12 сообщения проверки для переменной включает в себя такое же количество блоков 51 регистров проверки для переменной, как общее количество  блоков строки проверочной матрицы, показанной в равенстве (1), наряду с тем, что блок 51 регистров проверки для переменной включает в себя такое же количество  регистров 61, как размер циклической матрицы, составляющей проверочную матрицу.
t
1
t,2
2
2
0
t
1
t,2
2
(s)
(s)
(s)
(s)
Начальное состояние (значение в момент 0 времени) части данных сообщения, сохраненной в t-м регистре 61 в s-м блоке 51 регистров проверки для переменной, обозначено как L, (0), L (0), а начальное состояние данных, эквивалентных 1-битной информации P(s,t), обозначено как P(s,t). Каждые данные в момент j времени обозначены как L, (j), L (j), P(s,t) соответственно, где s, t и j обозначают целое число от 0 до m-1, целое число от 0 до a-1 и целое число от 1 до a соответственно.
t,1
t,2
2
(s)
(s)
Если допущено, что L (0) и L (0) в качестве начальных состояний являются наибольшими числами, которые могут быть представлены регистром 61, и что P(s,t)=0, каждые данные в момент j времени могут быть рассчитаны по каждым данным в момент j-1 времени в соответствии со следующими равенствами (17), (18) и (19):
[Равенство 17]
[Равенство 18]
[Равенство 19]
t-1
(s)
В вышеприведенных равенствах (17) и (18) W (j-1) обозначает набор, указанный следующим равенством (20):
[Равенство 20]
t,1
t-1
t,2
t-1
t-1
(s)
(s)
(s)
(s)
(s)
То есть L (j) в равенстве (17) является элементом с наименьшим значением среди элементов W (j-1), тогда как L (j) в равенстве (18) является элементом со вторым наименьшим значением среди элементов W (j-1). То есть из элементов W (j-1) элементы с наименьшим значением и со вторым наименьшим значением выбираются и удерживаются в регистре 61 следующей ступени.
0
j
Подобная обработка выполняется для μ(s,t) по равенству (16). То есть с начальным состоянием μ(s,t) в момент 0 времени данные μ(s,t) в момент j времени могут рассчитываться в соответствии со следующим равенством (21):
[Равенство 21]
t,1
t,2
2
j
j
(s)
(s)
В s-м блоке 51 регистров проверки для переменной формирователя 12 сообщения проверки для переменной данные, удерживаемые t-м регистром 61 в момент j времени, являются L (j), L (j), P(s,t) и μ(s,t). Блоком, в котором имеет место обработка обновления этих данных в каждый момент времени в соответствии с равенствами (17) и (21), является блок 62 узлов обработки проверки для переменной.
2-in
in
1-in
2-in
Далее пояснен блок 62 узлов обработки проверки для переменной. Блок 62 узлов обработки проверки для переменной принимает Z, cnt, P, μ, L и L в качестве входных данных.
2-in
2-in
1-in
1-in
2-in
in
Более точно, логический элемент 75 ИСКЛЮЧАЮЩЕЕ ИЛИ принимает информацию, указывающую плюс и минус P и которая указывает плюс и минус Z (самый старший двоичный разряд у Z). Компаратор 71 принимает L и абсолютное значение Z (биты иные, чем самый старший двоичный разряд у Z). Компаратор 72 принимает L и абсолютное значение Z. Абсолютное значение Z, L, L и выходные данные компаратора 71 подаются в качестве входных данных в селектор 73, который затем переключает свой выход в ответ на выходные результаты компаратора 71. Селектор 74 принимает cnt, μ и выходные данные компаратора 72 в качестве входных данных и переключает свои выходы в ответ на выходные результаты компаратора 72.
На фиг.7 факт деления Z на самый старший двоичный разряд (информацию, указывающую плюс или минус Z) и биты, иные, чем самый старший двоичный разряд (абсолютное значение Z), указан пустым ромбом. Самый старший двоичный разряд из Z подается на логический элемент 75 ИСКЛЮЧАЮЩЕЕ ИЛИ, тогда как биты, иные, чем самый старший двоичный разряд Z, подаются на компараторы 71, 72 и в селектор 73.
j-1
1-in
2-in
2-in
in
1-out
2-out
2-out
out
(i)
Z эквивалентен Z  по равенству 20, тогда как cnt указывает набор целого числа от 0 до n-1 и целого числа от 0 и a-1, соответствующий значению счета, синхронизированному с тактовыми импульсами. Блок 62 узлов обработки проверки для переменной выводит для выходных данных L, L, P и μ, L, L, P и μ, представленных следующими равенствами (22), (23), (24) и (25) соответственно:
[Равенство 22]
[Равенство 23]
[Равенство 24]
[Равенство 25]
1-out
1-out
1-in
out
То есть блок 62 узлов обработки проверки для переменной выводит наименьшее значение из значений Z, рассчитанных до сих пор, в качестве L через регистр 61 в блок 62 узлов обработки проверки для переменной следующей ступени. Когда значение L непосредственно предыдущей ступени, введенное в качестве L, стало наименьшим, как показано в равенстве (25), блок 62 узлов обработки проверки для переменной следующей ступени выводит в качестве μ набор целого числа от 0 до n-1 в качестве счета и целого числа между 0 и a-1, соответствующего значению счета, синхронизированного с тактовыми импульсами.
(s,0)
(s,1)
(s,2)
(s,n-1)
Обработка расчета, показанная равенствами с (17) по (21), может быть выражена размещением такого же количества блоков 62 узлов обработки проверки для переменной, как количество 1-иц в {gt, gt, gt,..., gt}, между t-м регистром 61 и (t+1)-м регистром 61 в s-м блоке 51 регистров проверки для переменной. Отмечено, что s и t обозначают целое число между 0 и m-1 и целое число между 0 и a-1 соответственно.
t,1
t,2
2
a
a
t,1
t,2
2
(s)
(s)
(s)
(s)
Согласно расчетам по равенствам с (17) по (21) данные L (a), L (a), P(s,t) и μ(s,t), удерживаемые в момент a времени в t-м регистре 61 s-го блока 51 регистров проверки для переменной, являются совпадающими с L  в равенстве (12), L  в равенстве (13), P(s,t) в равенстве 15 и μ(s,t) в равенстве 16, как указано следующими равенствами с (26) по (29):
[Равенство 26]
[Равенство 27]
[Равенство 28]
[Равенство 29]
a
t,1
t,2
2
a
a
(s)
(s)
В некоторый момент времени всеми входными данными, которые были приняты (момент  времени), данными, удерживаемыми в t-м регистре 61 в s-м блоке 51 регистров проверки для переменной формирователя 12 сообщения проверки для переменной, являются L (a), L (a), P(s,t) и μ(s,t). Эти данные выводятся из (a-1)-го регистра 61 каждого блока 51 регистров проверки для переменной в формирователь 11 сообщения переменной для проверки. Одновременно, в то время как выводятся эти данные, формирователь 12 сообщения проверки для переменной сдвигает данные, удерживаемые в j-м регистре 61, в (j+1)-й регистр 61, где j обозначает целое число от 0 до a-2, чтобы последовательно выводить данные через (a-1)-й регистр 61.
a
Инициализацией 0-го регистра 61 соответственные регистры инициализируются в момент времени, когда все операции вывода были завершены. Таким образом, для обработки ради формирования сообщения проверки для переменной  тактовых сигналов необходимы для операций обработки для ввода и сопровождающей его обработки и для вывода. Эти операции названы соответственно режимом обработки ввода и режимом вывода формирователя 11 сообщения переменной для проверки. Таким образом, посредством блоков, показанных на фиг.5-7, обработка формирования сообщения проверки для переменной может быть реализована без использования ОЗУ регистрами сдвига и блоками 62 узлов обработки проверки для переменной, каждый из которых сформирован, главным образом, из сумматоров и которые предусмотрены между соседними регистрами сдвига.
Между тем, формирователь 11 сообщения переменной для проверки, формирователь 12 сообщения проверки для переменной и узел 13 обработки нормализации каждый реализован полупроводниковым устройством, таким как ИС (интегральная схема). Отсюда каждый блок формирователя 11 сообщения переменной для проверки или каждый блок формирователя 12 сообщения проверки для переменной реализуются полупроводниковым устройством, таким как ИС.
Далее пояснена во всей полноте работа устройства декодирования по настоящему изобретению, показанного на фиг.1. Фиг.8 изображает схематический вид, показывающий работу устройства декодирования во всей его полноте.
Обработка устройством декодирования начинается с формирователя 11 сообщения переменной для проверки в режиме вывода и с формирователя 12 сообщения проверки для переменной в режиме обработки ввода.
В начале декодирования данные, удерживаемые регистрами 31 в блоках 21 регистров переменной для проверки, все инициализируются в 0. Данные, удерживаемые в регистрах 61 блока 51 регистров проверки для переменной, также инициализируются.
a
la+r
Поскольку все данные, удерживаемые регистрами 31 блоков 21 регистров переменной для проверки, были инициализированы в 0, при запуске, данные сообщения, подаваемые в качестве выходных данных формирователем 11 сообщения переменной для проверки в формирователь 12 сообщения проверки для переменной в течение времени, начиная с запуска и до тех пор, пока не истекли  тактов, являются совпадающими с принятыми данными F, где l и r указывают целое число от 0 до n-1 и целое число от 0 до a-1 соответственно.
a
la+r
Когда истекло  тактов, вывод данных сообщения формирователем 11 сообщения переменной для проверки в формирователь 12 сообщения проверки для переменной приходит к окончанию. В этот момент времени 1 бит, представляющий плюс или минус у F, был установлен (сохранен) регистром 31 в блоке 21 регистров переменной для проверки, как упомянуто выше, наряду с тем, что данные, которые должны выводиться следующими в формирователь 12 сообщения проверки для переменной, удерживаются регистрами 61 в блоке 51 регистров проверки для переменной.
a
Режим обработки ввода и режим вывода затем переключаются каждые  тактов, как показано на фиг.8. То есть вывод данных сообщения в формирователь 11 сообщения переменной для проверки формирователем 12 сообщения проверки для переменной и вывод данных сообщения из формирователя 11 сообщения переменной для проверки в формирователь 12 сообщения проверки для переменной выполняются поочередно.
В соответственных режимах формирователь 12 сообщения проверки для переменной и формирователь 11 сообщения переменной для проверки повторяют вышеприведенную обработку заданное количество раз. В заключение формирователь 11 сообщения переменной для проверки устанавливается в режим вывода наряду с тем, что формирователь 12 устанавливается в режим обработки ввода. Формирователь 11 сообщения переменной для проверки последовательно выводит один бит, представляющий плюс или минус выходных данных, в качестве выходных данных устройства декодирования.
2
Между тем, данные P(s,t), обрабатываемые формирователем сообщения проверки для переменной, могут использоваться в качестве данных для принятия решения, в качестве результата вышеприведенной обработки декодирования, были или нет исправлены ошибки, содержащиеся в принятых данных.
С настоящим примерным вариантом осуществления, описанным выше, обработка расчета сообщения переменной для проверки и оцененных битов передачи может выполняться многочисленным количеством регистров 31 и блоков 32 узлов обработки переменной для проверки без использования ОЗУ. Блоки 32 узлов обработки переменной для проверки, каждый, главным образом, составлены из сумматора 41 и предусмотрены между соседними регистрами 31.
Дополнительно с настоящим примерным вариантом осуществления обработка расчета сообщения проверки для переменной может выполняться регистрами 61 и блоками 62 узлов обработки проверки для переменной без использования ОЗУ. Блоки узлов обработки проверки для переменной, каждый, составлены, главным образом, из компаратора и скомпонованы между соседними регистрами 61.
Устройство декодирования повторяет вышеприведенную обработку, чтобы декодировать входную последовательность принятых данных для вывода оцененной последовательности битов для передачи. Таким образом, с устройством декодирования упрощенной конфигурации, не применяющей ОЗУ, возможно декодировать входную последовательность принятых данных на высокой скорости, чтобы выводить оцененную последовательность битов передачи без ограничений, накладываемых скоростью доступа к ОЗУ.
2
Более того, с настоящим примерным вариантом осуществления данные P(s,t), обрабатываемые формирователем 12 сообщения проверки для переменной, могут использоваться в качестве данных для принятия решения, исправимы или нет ошибки, содержащиеся в принятых данных.
Пример конфигурации устройства декодирования для кодов с контролем четности низкой плотности, применяющего ОЗУ в качестве устройства памяти, далее описан со ссылкой на чертежи. Фиг.9 - структурная схема, показывающая пример конфигурации устройства декодирования для кодов с контролем четности низкой плотности, использующего ОЗУ. Это устройство декодирования включает в себя не показанное ОЗУ, блок 84 памяти сообщений, контроллер 82 формирования адреса и процессор 83 узла проверки. ОЗУ является устройством памяти для удерживания принятых данных в качестве объекта исправления ошибок. Блок памяти сообщений реализован посредством ОЗУ в качестве устройства памяти для удерживания данных, сформированных в ходе декодирования и которые названы сообщением. Контроллер формирования адреса формирует и управляет адресами ОЗУ, а процессор узла проверки используется для обновления сообщения.
Сообщение грубо делится на сообщение переменной для проверки и сообщение проверки для переменной. Оба из этих сообщений могут дополнительно подразделяться. Если количество строк и количество столбцов в проверочной матрице H являются M и N соответственно, причем каждое из M и N является положительным целым числом, сообщение переменной для проверки классифицируется в Zi,j, наряду с тем, что сообщение проверки для переменной классифицируется в Li,j.
Суффиксы i и j обозначают целое число от 0 до M-1 и целое число от 0 до N-1 соответственно. Обращено внимание, что i представляет компоненты вектор-строк или вектор-столбцов проверочной матрицы, а j представляет компоненты вектор-столбцов или вектор-строк проверочной матрицы. Процессор 81 узла переменной обновляет сообщение переменной для проверки из сообщения проверки для переменной и принятых данных. Детали обработки узла переменной могут быть представлены следующим равенством (30):
[Равенство 30]
В вышеприведенном равенстве j является целым числом от 0 до N-1, i обозначает целое число от 0 до M-1, Fj обозначает соответствующие принятые данные, а i' является целым числом от 0 до M-1, не совпадающим с i, и покрывает все целые числа, элементы которых в вектор-строке проверочной матрицы, соответствующей j, являются 1. Процессор 83 узла проверки обновляет сообщение проверки для переменной из сообщения переменной для проверки. Детали обработки узла проверки представлены следующим равенством (31):
[Равенство 31]
В вышеприведенном равенстве j обозначает целое число от 0 до N-1, i обозначает целое число от 0 до M-1, Pi,j обозначает 0 или 1, а j' обозначает целые числа от 0 до N-1, не совпадающие с j, и покрывает все целые числа, элементы которых в вектор-строке проверочной матрицы, соответствующей i, являются 1.
Если, в случае кодов с контролем четности низкой плотности, проверочная матрица которого является блоком циклической матрицы (псевдоциклический код с контролем четности низкой плотности), используется упорядоченность проверочной матрицы, часть суммы равенства (30) и индекс части вычисления наименьшего значения по равенству (31) могут быть структурированы для упрощения формирования адреса для доступа к ОЗУ.
Второй примерный вариант осуществления
Далее описан второй примерный вариант осуществления по настоящему изобретению. В начале описана роль μ(s,t), где s и t обозначают целое число от 0 до m-1 и целое число от 0 до a-1 соответственно, в качестве одного из четырех видов данных, рассчитываемых формирователем 12 сообщения проверки для переменной, описанным выше в связи с первым примерным вариантом осуществления.
t,1
t,2
(s)
(s)
Данные μ(s,t) являются набором из двух целых чисел, то есть целого числа от 0 до n-1 и целого числа от 0 до a-1, и необходимы для принятия решения о том, какие из двух данных L  и L , выводимых формирователем 12 сообщения проверки для переменной, должны суммироваться при обработке равенства (7), выполняемого формирователем 12 сообщения проверки для переменной.
t,1
t,2
t
(s)
(s)
(s)
Как упомянуто выше, L  и L  обозначают элементы набора W  по равенству (14), имеющему наименьшее значение и второе наименьшее значение соответственно. Если обработка формирователем 11 сообщения переменной для проверки, показанная равенством (7), замещается следующим равенством (32), значение, рассчитанное этой операцией, хотя и зависимое от выбора проверочных матриц (равенства 1 и равенства 2), довольно хорошо аппроксимирует значение, рассчитываемое согласно равенству (7).
[Равенство 32]
t
(s)
То есть, поскольку оно не является обоими, элементом с наименьшим значением и элементом со вторым наименьшим значением, из элементов набора W  в равенстве (14), а только элементом со вторым наименьшим значением, который используется, не обязательно рассчитывать μ(s,t) формирователем 12 сообщения проверки для переменной.
Таким образом, можно снизить битовую разрядность регистров 61 в блоке 51 регистров проверки для переменной или упростить конфигурации блоков 62 узлов обработки проверки для переменной или блока 32 узлов переменной для проверки, тем самым уменьшая размер устройства, взятого в целом, и упрощая обработку.
Фиг.10 - структурная схема, показывающая пример конфигурации упрощенного блока 32 узлов обработки переменной для проверки.
2
1-in
in
1-in
Со ссылкой на фиг.10, упрощенный блок 32 узлов обработки переменной для проверки включает в себя инвертор 102 плюса и минуса, сумматор 101 и логический элемент 103 ИСКЛЮЧАЮЩЕЕ ИЛИ. Логический элемент 103 ИСКЛЮЧАЮЩЕЕ ИЛИ снабжается P и P. Инвертор 102 плюса и минуса снабжается L2 и выходными данными логического элемента 103 ИСКЛЮЧАЮЩЕЕ ИЛИ. Сумматор 101 снабжается Z и выходными данными инвертора 102 плюса и минуса. Отмечено, что, поскольку входные/выходные данные, показанные на фиг.10, эквивалентны данным, указанным одинаковыми символами, такими как P, описание опущено.
1
Поскольку упрощенный блок 32 узлов обработки переменной для проверки не нуждается во входных данных μ или L, его конфигурация упрощена по сравнению с блоком 32 узлов обработки переменной для проверки по первому варианту осуществления, показанному на фиг.4, таким образом, давая возможность сокращаться битовым разрядностям регистров 31 в соответствующем блоке 21 регистров переменной для проверки.
Фиг.11 - структурная схема, показывающая пример конфигурации упрощенного блока 62 узлов обработки проверки для переменной.
2-in
2-in
1-in
2-in
Со ссылкой на фиг.11, упрощенный блок 62 узлов обработки проверки для переменной включает в себя селектор 113 и компараторы 111 и 112. Логический элемент 114 ИСКЛЮЧАЮЩЕЕ ИЛИ принимает информацию, указывающую плюс или минус Z (самый старший двоичный разряд у Z) и P. Компаратор 111 снабжается абсолютным значением Z (битами, иными, чем самый старший двоичный разряд у Z). Компаратор 112 снабжается абсолютным значением Z и L. Селектор 113 снабжается абсолютным значением Z, L и L, выходными данными компаратора 111 и выходными данными компаратора 112.
На фиг.11 факт деления Z на самый старший двоичный разряд (информацию, указывающую плюс или минус Z) и биты, иные, чем самый старший двоичный разряд (абсолютное значение Z), указан пустым ромбом. Самый старший двоичный разряд у Z подается на логический элемент 75 ИСКЛЮЧАЮЩЕЕ ИЛИ, тогда как биты, иные, чем самый старший двоичный разряд Z, подаются на компараторы 111, 112 и в селектор 113.
2-in
Обращено внимание, что входные/выходные данные, показанные на фиг.11, эквивалентны данным, представленным теми же самыми символами, такими как P, и поэтому описание таких входных данных опущено для краткости.
Как описано выше, упрощенный блок 62 узлов обработки проверки для переменной не нуждается во входных данных μ и поэтому является более простым по конфигурации, чем блок 62 узлов обработки проверки для переменной по первому примерному варианту осуществления, показанному на фиг.7. Возможно снижать битовую разрядность регистра 61 в блоке 51 регистров проверки для переменной.
С настоящим примерным вариантом осуществления, описанным выше, можно снижать количество регистров 61 в блоке 51 регистров проверки для переменной, таким образом уменьшая размер устройства декодирования, взятого в целом, и упрощая обработку.
Между тем, если расчеты выполняются в соответствии со следующим равенством (33), данные сообщения могут рассчитываться до более высокой точности, чем с равенством (32), и с более простой обработкой, чем с равенством (7).
[Равенство 33]
1-out
1-in
В равенстве (33) μ'(i,j) является целым числом от 0 до a-1. Блок 62 узлов обработки проверки для переменной выводит μ'(i,j) при временной привязке, подобной таковой по первому примерному варианту осуществления, то есть при временной привязке, когда значение L предыдущей ступени, введенное в качестве L, стало наименьшим значением. Должно быть отмечено, что μ'(i,j) уменьшены по объему информации по сравнению со случаем, где μ(i,j) в равенствах (7) и (25) по первому примерному варианту осуществления обозначает набор из целого числа между 0 и n-1 и целого числа между 0 и a-1, таким образом соответственно понижая точность расчета данных сообщения переменной для проверки.
Базовые конфигурации блока 62 узлов обработки проверки для переменной и блока 32 узлов обработки переменой для проверки являются такими же, как фиг.7 и 4 для первого примерного варианта осуществления. Однако возможно уменьшать битовую разрядность каждого регистра 61 в блоке 51 регистров проверки для переменной и отсюда размер устройства декодирования, взятого в целом.
Как обсуждено выше, если используется равенство (33), может выбираться равновесие между точностью расчета и размером устройства при компромиссе между точностью расчета и размером устройства, при условии выбора μ(s,t), из трех альтернативных вариантов (с использованием μ(s,t), как в первом примерном варианте осуществления, с использованием μ'(i,j), как во втором примерном варианте осуществления, или без использования μ).
Первый примерный вариант осуществления
Фиг.12 - структурная схема, показывающая пример конфигурации устройства (хранения) передачи данных, использующего декодер 128 по настоящему изобретению.
Устройство (хранения) передачи данных включает в себя устройство 121 передачи данных и устройство 125 приема данных (приемник). Устройство 121 передачи данных включает в себя кодировщик 122 для псевдоциклических кодов с контролем четности низкой плотности, контроллер синхронизации/преобразователь 123 данных (преобразователь управляющих данных синхронизации) для управления синхронизацией кадра и для преобразования в данные, подходящие к модулятору 124, и модулятор 124. Модулятор 124 выводит информацию в тракт связи или в память.
Устройство 125 приема данных включает в себя демодулятор 126 для демодуляции информации, принятой из тракта связи или из памяти, преобразователь 127 управляющих данных синхронизации для преобразования выходных данных демодулятора 126 во входные данные декодера 126 и для осуществления синхронизации кадра и декодер 128 по настоящему изобретению.
n
m
Если в качестве числового примера общим количеством  блоков столбца проверочной матрицы является 65, общим количеством  блоков строки проверочной матрицы является 8, а размером циклической матрицы является 63, последовательность битов с длиной кадра в 4095 битов может делаться структурным элементом кадра.
0
1
a-1
(i,j)
(i,j)
(i,j)
Предполагается, что вес вектор-строки каждого блока в проверочной матрице, показанной равенством (2), (f , f ,..., f ) является меньшим чем 1, где i обозначает целое число от 0 до 7, а j обозначает целое число от 0 до 64. Также предполагается, что количество блоков 32 узлов обработки переменной для проверки, скомпонованных между соседними регистрами 31, из многочисленного количества регистров 31, включенных в каждый из 65 блоков 21 регистров переменной для проверки, является не большим чем два.
Обработка сотен мегабит в секунду может реализовываться при размере устройства в сотни тысяч логических элементов.
ПРОМЫШЛЕННАЯ ПРИМЕНИМОСТЬ
Настоящее изобретение может использоваться в качестве технологии исправления ошибок для удовлетворения требований к конфигурации системы, таких как снижение потребной мощности в системах спутниковой связи или мобильной связи или уменьшение размера антенны. Настоящее изобретение также может использоваться в качестве технологии исправления ошибок для улучшения надежности устройств памяти, таких как таковые при магнитной записи.