СПОСОБ И УСТРОЙСТВО ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ДАННЫХ Российский патент 2012 года по МПК H03M13/27 

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

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

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

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

Одним способом, используемым для исправления ошибок, является турбокодирование блока информации перед его передачей по каналу. При использовании такого способа кодер в передатчике системы связи кодирует входной блок u длины K' битов в блок x кодового слова из N битов. После этого блок кодового слова передается по каналу, возможно, после дальнейшей обработки, например, перемежения в канале, как определено в спецификациях IEEE 802.16e. В приемнике турбодекодер воспринимает принятый вектор y сигнала длины N как входной сигнал и формирует оценку û вектора u.

Как правило, турбокодер состоит из двух компонентных сверточных кодеров. Первый компонентный кодер принимает входной блок u как входные данные в исходном порядке, а второй компонентный кодер принимает входной блок u в перемеженном порядке после прохождения u через турбоперемежитель π. Выход x турбокодера состоит из систематических битов (равных входному блоку u), битов четности из первого компонентного кодера и битов четности из второго компонентного кодера.

Соответственно турбодекодер в приемнике системы связи состоит из двух компонентных сверточных декодеров, один для каждого компонентного кода. Компонентные декодеры разделены перемежителем π и соответствующим деперемежителем π^-1. Сообщения в формате логарифмических отношений правдоподобия (LLR) итерационно передаются между компонентными декодерами. После нескольких итераций принимается решение û.

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

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

Фиг.1 - блок-схема передатчика.

Фиг.2 - блок-схема турбокодера по фиг.1.

Фиг.3 - блок-схема приемника.

Фиг.4 - блок-схема турбодекодера по фиг.4.

Фиг.5 - блок-схема, изображающая работу передатчика по фиг.1.

Фиг.6 - блок-схема, изображающая работу приемника по фиг.3.

Подробное описание чертежей

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

Во время работы принимается блок информации размера K. Определяется перемежитель размера K', где K' связано с K", где K" - из набора размеров, причем этот набор размеров содержит K" = a^p × f, p_mm ≤ p ≤ p_max, f_min ≤ f ≤ f_max, где a - целое число, f - постоянное целое число между f_min и f_max, и p принимает целочисленные значения между p_min и p_max, a>1, p_max> p_min, p_min>l. Блок информации размера K вставляется во входной блок размера K'. Входной блок перемежается с использованием перемежителя размера K'. Исходный входной блок и перемеженный входной блок кодируются для получения блока кодового слова. Блок кодового слова передается через канал.

В последующем варианте осуществления настоящего изобретения этап определения размера K' перемежителя, который связан с K", содержит этап использования K' = K".

В еще одном варианте осуществления настоящего изобретения этап определения размера K' перемежителя, который связан с K", содержит этап использования K' = K", когда K" не является числом, кратным (2^m-l), иначе используется K' =K" + δ(K"), когда K" является числом, кратным (2^m-1), причем m - длина памяти компонентного сверточного кодера и δ(K") - небольшое положительное или отрицательное целое число, не равное числу, кратному (2^m-l). В одном варианте осуществления m=3.

В еще одном варианте осуществления настоящего изобретения этап перемежения входного блока содержит этап использования перестановки π(i) = (iP₀ + A + d(i)) mod K', где 0 ≤ i ≤ K'-l является порядковым индексом позиций символа после перемежения, π(i) - индекс символа до перемежения, соответствующий позиции i, K' - размер перемежителя в символах, P₀ - число, взаимно простое с K', A - константа, C - небольшое число, на которое делится K', и d(i) - вектор размывания вида d(i) = α(i mod C) + P₀ × β(i mod C), где α(·) и β(·) - векторы, каждый длины C, периодически используемые для 0 ≤ i ≤ K'-1.

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

- K обозначает размер блока информации.

- K' обозначает размер перемежителя (т.е. размер входного блока, для которого определяется перемежитель турбокода).

- K" обозначает вспомогательную переменную, которая может использоваться в определении размера перемежителя.

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

- R обозначает родительскую скорость кодирования турбокодера (например, R = 1/3 для 3GPP турбокода).

- R^-1 обозначает обратную величину родительской скорости кодирования турбокодера (например, R^-1 = 3 для 3GPP турбокода).

- N_TB - количество битов концевой комбинации в закодированном блоке. В частности, для 3GPP турбокода:

N_TB = 12 для 3GPP турбокода с концевой комбинацией битов,

N_TB = 0 для 3GPP турбокода с циклически замкнутыми компонентными сверточными кодами.

- π обозначает внутренний перемежитель турбокода.

- Операция округления в меньшую сторону обозначает наибольшее целое число меньше x, и операция округления в большую сторону обозначает наименьшее целое число больше x.

- u обозначает входной блок, длина которого равна K' и который отправляется в турбокодер в передатчике, û обозначает оцененный входной блок, длина которого равна K' и который формируется турбодекодером в приемниκе. Заметим, что при отсутствии ошибок декодирования û=u. Иначе û≠u.

Обратимся теперь к чертежам, на которых одинаковые компоненты обозначены одинаковыми позициями, фиг.1 является блок-схемой передатчика 100. Как изображено, передатчик 100 содержит схему 109 вставки заполнителей, турбокодер 101, схему 103 определения размера перемежителя, таблицу 105 параметров перемежителя и передатчик 107. Кодер 101 предпочтительно является турбокодером 3GPP со скоростью 1/3, однако способы, описанные здесь для управления кодером 101, могут быть применены к другим кодерам, включающим в себя, например, турбокодеры, выполняющие турбокодирование с концевой комбинацией битов или без нее, циклически замкнутые, двоичные или двойные бинарные турбокодеры, турбокодеры с использованием различных способов согласования скорости и выкалывания… и т.д. Схема 103 определяет размер K' перемежителя, который связан с K", где K" - из набора размеров, причем набор размеров содержит K" = a^p × f, p_min ≤ p ≤ p_max, f_min ≤ f ≤ f_max, где a - целое число, f - постоянное целое число между f_min и f_max, и p принимает целочисленные значения между p_min и p_max, a>1, p_max> p_min, p_min> 1.

Во время работы передатчика 100 блок информации размера K должен быть закодирован турбокодером 101. Для некоторых систем связи, где используется большое количество различных K, не рационально (и часто невозможно) определить бесконфликтный (CF) перемежитель для каждого размера K блока информации. Предпочтительно, если небольшой набор (K') хорошо спроектированных CF перемежителей может охватить все размеры блока информации. С учетом размера K блока информации, посредством схемы 103 может быть выбран надлежащий размер K' перемежителя из набора размеров (например, размеров перемежителя, перечисленных в таблице 105). После этого блок информации вставляется во входной блок размера K' схемой 109 и отправляется в качестве входных данных в турбокодер 101. Обычно вставляется блок информации с K_finer битами-заполнителями (через схему 109 вставки заполнителя). Заметим, что термины "размер" и "длина" используются как синонимы для указания количества элементов в блоке или векторе.

После выбора K' посредством схемы 103 оно обеспечивается в турбокодер 101. Во время кодирования можно использовать бесконфликтный перемежитель (на фиг.1 не изображен). Например, перемежитель может использовать перестановку π(i) =(iP₀+A+d(i)) mod K', где 0≤i≤K'-1 является порядковым индексом позиций символа после перемежения, π(i) - индекс символа до перемежения, соответствующий позиции i, K' - размер перемежителя в символах, P₀ - число, взаимно простое с K', A - константа, C - небольшое число, на которое делится K', и d(i) - вектор «размывания» вида d(i) = α(i mod C) + P₀ × β(i mod C), где α(·) и β(·) - векторы, каждый длины C, периодически используемые для 0 ≤ i ≤ K'-1. В общем, символ может состоять из множества битов, и на этапе перемежения можно использовать дополнительный этап перестановки битов в символе. Не нарушая общности, в нижеследующем обсуждении рассматривается типичный случай, где символ состоит только из одного бита (соответственно, не требуется перестановка битов в символе), и термины "бит" и "символ" могут быть использованы как синонимы.

Вывод турбокодера 101 содержит блок x кодового слова, и x отправляется в передатчик 107, откуда оно передается через канал. Передатчик может выполнять дополнительную обработку, например согласование скорости, перемежение канала, модуляцию и т.д., до передачи блока x кодового слова через канал.

Фиг.2 является блок-схемой кодера 101 по фиг.1. Как изображено, кодер 101 содержит перемежитель 201, схему 202 кодирования и схему 203 кодирования. Перемежитель 201 может быть бесконфликтным перемежителем. Будем считать, что перемежитель π(i), 0 ≤ i< K', бесконфликтный для размера W окна, тогда и только тогда, когда он удовлетворяет следующему ограничению и для ψ=π (перемежитель), и для ψ=π^-1 (деперемежитель),

(1),

где 0≤j<W, 0≤t, ν<M(=K'|W) и t≠ν. Хотя в этом не всегда есть необходимость, для эффективного проектирования турбодекодера, как правило, все M окон являются заполненными, где K'=MW. Члены в (1) являются адресами группы блоков памяти, к которым одновременно обращаются M процессоров при записи внешних значений в выходные группы блоков памяти во время итерационного декодирования. Если все эти адреса группы блоков памяти являются уникальными во время каждой из операций чтения и записи, то во время доступа к памяти конфликты не происходят и, следовательно, можно избежать задержки (де)перемежения, что приводит к реализации высокоскоростного декодера.

Во время работы турбокодера 101 входной блок длины K' битов вводится и в перемежитель 201, и в схему 202 кодирования. Перемежитель 201 может быть бесконфликтным перемежителем размера K'.

Перемежитель 201 перемежает входной блок и передает его в перемеженном порядке в схему 203 кодирования. После этого схема 203 кодирования кодирует перемеженный входной блок. Аналогично, схема 202 кодирования кодирует исходный входной блок. Блок кодового слова x состоит из систематического блока (равного входному блоку), выхода схемы 202 кодирования и выхода схемы 203 кодирования. После этого блок кодового слова x отправляется в передатчик 107, который может также принимать копию входного блока непосредственно.

В следующем выражении в качестве примера бесконфликтного перемежителя дан перемежитель с почти регулярной перестановкой (ARP)

π(i) = (iP₀ + A + d(i))mod K',

где 0≤i≤K'-1 является порядковым индексом позиций бита после перемежения, π(i) - индекс бита до перемежения, соответствующий позиции i, K' - размер перемежителя, P₀ - число, взаимно простое с K', A - константа, C - небольшое число, на которое делится K', и d(i) - вектор размывания вида d (i) = α(i mod C) + P₀ × β(i mod C), где α(·) и β(·) - векторы, каждый длины C, периодически используемые для 0<i<K'-1. И α(·), и β(·) состоят из чисел, кратных C. Общий перемежитель π(·), созданный соответственно, обладает квазициклическими (то есть периодическими) свойствами с периодом C, и при использовании в циклически замкнутых (tail-biting) турбокодах сам турбокод становится квазициклическим, что приводит к упрощенной процедуре проектирования кодов.

Если перемежитель 201 может удовлетворять (1) для различных значений M, то декодер может быть реализован c использованием различной степени параллелизма (одной для каждого M). Соответственно, требуется выбрать K' с различными множителями. Для перемежителя ARP длины K' любой размер W окна, где W - число, кратное C, и множитель K' можно использовать для высокоскоростного декодирования без конфликтов при обращении к памяти. Это обеспечивает гибкость и масштабируемость при проектировании декодера с обеспечением возможности широкого диапазона множителей M параллелизма. Соответственно, можно достичь хорошего компромисса между скоростью декодирования и сложностью на основе требований к системе (или классам пользовательских элементов).

Выбор размера K' перемежителя

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

Требуется, чтобы количество битов-заполнителей K_filler, вставляемых в блок информации для формирования входного блока, было ограничено до небольшого процента (например, приблизительно 10-13%) от размера K блока информации. Это достигается посредством ограничения разности между смежными размерами перемежителя, то есть смежными значениями K' (с предположением, что все доступные K' значения отсортированы в порядке возрастания). Количество битов-заполнителей минимизируется посредством выбора такого наименьшего доступного K', что K'≥K. Количество битов-заполнителей равно K_filler=K'-K. Однако если требуется, также могут быть выбраны другие значения K'≥K.

Рассмотрим следующий набор размеров, определенных для охвата размеров информации между K_min и K_max

K" = a^p × f, P_min ≤ P ≤ P_max, f_min ≤ f ≤ f_max, (2)

где a - целое число, f - постоянное целое число между f_min и f_max, и p принимает целочисленные значения между p_min и p_max, a>l, p_max>p_min, p_min>l. Хотя в этом нет необходимости, можно выбирать эти параметры так, что K_min = a^Pmin × f_min и K_max = a^Pmax × f_max, при этом отбрасываются любые размеры, которые могут не являться необходимыми. Этот способ выбора ограниченного набора размеров для охвата диапазона размеров блока информации называется полулогарифмической фрагментацией. Для заданного блока информации размера K, размер K' (связан) с K" на основе таблицы полулогарифмической фрагментации и размером K входного блока (Для ясности, в остальной части обсуждения предполагается, что значения полулогарифмической фрагментации содержат все допустимые размеры перемежителя (то есть K' =K"), хотя, в общем, это не обязательно).

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

Из нескольких способов выбора параметров одним способом выбора значений f_min и f_max является обеспечение того, чтобы значения K', получающиеся из смежных p, находились на одной линии друг с другом, то есть a^p × (f_max + l) = a^p+1 × f_min, соответственно,

f_max = a × f_min-1

Для данного значения p интервал между двумя смежными размерами блока задается a^p, что означает, что добавляется максимум a^p-1 битов-заполнителей, если размер K блока информации находится в группе p. Соответственно, отношение битов-заполнителей K_filter к размеру K блока информации ограничено, как показано ниже, что имеет место, когда размер K блока немного больше, чем размер, задаваемый (p, f_min), и использование K', задаваемого (p, f_min+l) для

В качестве альтернативы, значения K', получающиеся из смежных p, можно расположить на одной линии друг с другом посредством a^p × f_max =a^p+1 × (f_min-1), что в результате приводит к f_max = a × (f_min-l). Это дало бы аналогичное ограничение K_filler/K. Следовательно, параметры для полулогарифмической фрагментации могут быть настроены согласно диапазону поддерживаемых размеров блока, а также относительно допустимой доли битов-заполнителей. При выборе f_min требуется баланс между следующими двумя требованиями:

- f_min должно быть большим для уменьшения доли битов-заполнителей,

- f_min должно быть небольшим для ограничения размера таблицы перемежителя, так как количество размеров блока, определенных для каждого p, равно f_max-f_min + 1 = (a-l) × f_min.

После определения размеров (K") полулогарифмического фрагмента размер K' перемежителя может быть получен из полулогарифмических размеров фрагмента (без существенного отклонения), например,

1. С использованием K' = K".

2. С использованием K' = K", когда K" не является числом, кратным (2^m-l), иначе с использованием K' = K" + δ (K"), когда K" является числом, кратным (2^m-l), где m - длина памяти компонентного сверточного кодера и δ(K") - небольшое положительное или отрицательное целое число, не равное числу, кратному (2^m-l). Это полезно, если компонентные сверточные коды являются циклически замкнутыми (tail-biting), где недопустимы числа, кратные (2^m-l).

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

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

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

Способ полулогарифмической фрагментации очень прост в том смысле, что для любого размера блока размер K' перемежителя, который должен использоваться, может быть легко определен на основе K", вычисленного из (2). Например, в одной схеме размеры полулогарифмического фрагмента могут использоваться как допустимые размеры перемежителя непосредственно. Любые специальные размеры блока также могут быть очень легко обработаны.

Размеры, определенные способом (2) полулогарифмической фрагментации, могут иногда включать в себя размеры, которые являются неподходящими размерами перемежителя для турбокодирования. Например, циклически замкнутая (tail-biting) версия турбокодера (w=3) 3GPP с восемью состояниями не поддерживает размеры входного блока (то есть размеры перемежителя), которые являются числами, кратными 7 (то есть 2^m-l). В таких случаях, каждый раз, когда в результате уравнения (2) получается размер, который является числом, кратным 2^m-l, из него вычитается или к нему добавляется такое небольшое значение, что получающийся в результате размер больше не является числом, кратным 2^m-l.

Например, если a=2, f_min=8 и f_max=l5, то размеры перемежителя вида K'=K"=2^p×l4 являются числами, кратными 7, и, следовательно, являются недопустимыми размерами перемежителя при использовании циклически замкнутого (tail-biting) 3GPP TC. Следовательно, этот случай должен обрабатываться с небольшим изменением, например, с использованием K'=K", когда K" не является числом, кратным 7, иначе с использованием K'=K"+δ(K"), когда K" является числом, кратным 7, и δ(K") является небольшим положительным или отрицательным целым числом, не равным числу, кратному 7.

Для размеров K", которые являются недопустимым выбором для перемежителей ARP, одним простым способом определения связанного размера K' перемежителя является вычитание (сложение только когда допустимо) d×C из K", где d - небольшое положительное целое число, и d не является числом, кратным 7, и C - длина цикла перемежителя ARP, используемая для размеров блока, близкая к K'. (Вспомним, что размер блока перемежителя ARP является числом, кратным длинам C цикла.) Другими словами,

K'=K"-dC (3)

или

K'=K"+dC (4),

когда K" является числом, кратным 7. Так как C обычно является четным целым числом, например 4, 8, 12 или 16, то эта регулировка дает два преимущества, а именно (a) K' не является числом, кратным 7, и (b) K' является числом, кратным C, и, следовательно, можно спроектировать перемежитель ARP для размера K'.

Для простоты, для всех K", для которых требуется регулировка, можно выбирать одинаковое d. Одним важным соображением при выборе d является то, что оно должно быть таким, что все размеры, получаемые посредством (3) или (4), имеют значительное количество множителей, что обеспечивает возможность поддерживать широкий диапазон параллелизма для CF перемежителя, определенного соответственно.

Пример выбора размера перемежителя ARP

В таблице 1 представлен набор CF перемежителей ARP, подходящих для охвата размеров блока информации для 3GPP долгосрочного развития (LTE). Размеры перемежителя, имеющиеся в таблице 105, определены на основе способа полулогарифмической фрагментации, описанного выше. А именно

K"=2^p × f, p=4,5,…,9; f=8, 9,…, 15, (5)

и K' определяется из K". Размеры перемежителя определяются следующим образом: с использованием K'=K" и для p=4, 5, 6, 7, 8, 9 и f=8, 9, 10, 11, 12, 13, 15, и с использованием K'=K"-dC для p=4,5,6,7,8,9 и для f=14, для охвата K от 128 до 7680. Последние три размера (f=13,14,15), соответствующие p=9, могут быть удалены, чтобы K_max=6144, с K_min=128. Уравнение (3) используется вместе с d=2, когда f=14 (то есть, чтобы избежать размеров перемежителя, которые являются числами, кратными 7) для обработки циклически замкнутого (tail-biting) TC. В таблице 1 эти размеры выделены. После определения размеров перемежителя в 105 для каждого размера перемежителя можно спроектировать CF перемежитель.

С учетом любого размера K блока информации схема 103 может определять размер K' перемежителя, используемый для K при выборе наименьшего значения K' из 105, которое больше или равно K. При известном K' и f_min = 2^b, f_max =2^b+1-l, параметры p и f могут быть вычислены следующим образом:

(6)

(7)

В частности, для параметров в (5),

(8)

С параметрами p и f размер K' блока может быть вычислен с использованием (2) или (5), и, кроме того, когда f является числом, кратным 7, размер перемежителя, вычисленный с использованием (3) или (4), может использоваться дополнительно, когда используется циклически замкнутое (tail-biting) кодирование. После этого ищутся параметры, связанные с размером K' перемежителя, в запоминающем устройстве для параметра 105 перемежителя, который обычно хранится в памяти для устройства связи.

Запоминающее устройство для параметра 105 перемежителя может хранить параметры перемежителя ARP с использованием значений K', C, P₀, α(·) и β(·), которые берутся, по меньшей мере, из одной строки таблицы 1. Перемежитель 201 может использовать перемежитель ARP, использующий значения K', C, P₀, α(·) и β(·), которые берутся, по меньшей мере, из одной строки таблицы 1.

Таблица 1
Таблица параметров перемежителя для перемежителей ARP с A=3 Размер K' перемежителя C P₀ α β 128 4 81 4 0 0 4         0 20 120 68         144 4 91 4 0 4 0         0 76 20 52         160 4 123 4 4 0 0         0 4 8 12         176 4 127 4 4 0 0         0 12 112 44         192 4 169 4 0 4 0         0 8 4 16         208 4 37 4 0 4 0         0 68 20 164         216 4 121 4 4 0 0         0 68 12 28         240 4 161 0 0 4 4         0 16 196 212         256 4 31 0 0 4 4         0 60 8 68         288 4 131 0 4 0 4         0 80 144 36         320 4 69 0 0 4 4         0 4 8 12         352 4 35 4 0 0 4         0 48 96 152         384 4 91 0 0 4 4         0 4 20 24         416 4 31 4 4 0 0         0 24 28 60         440 4 53 0 4 4 0         0 4 20 216         480 4 53 0 4 4 0         0 72 192 12         512 4 273 0 0 4 4         0 20 8 24         576 4 29 0 0 4 4         0 64 120 68         640 4 147 0 0 4 4         0 24 12 4         704 4 309 0 0 4 4         0 4 12 8         768 4 241 0 0 4 4         0 4 12 8         832 4 53 0 0 4 4         0 4 12 8         888 7 77 0 4 4 0         0 48 64 140         960 4 143 0 0 4 4         0 4 12 8         1024 8 245 8 0 8 8 0 0 8 0 0 8 40 16 96 80 56 88 1152 8 119 0 0 8 0 8 0 8 8 0 8 40 64 80 48 24 88 1280 8 897 0 0 8 0 8 0 8 8 0 8 96 88 32 16 48 40 1408 8 593 0 8 0 8 8 0 8 0 0 8 96 48 32 16 80 40 1536 8 1139 0 0 8 0 8 0 8 8 0 16 56 88 80 24 72 64 1664 8 1451 0 8 0 8 8 0 8 0 0 16 40 96 88 80 32 48 1776 8 115 8 0 0 0 0 8 8 8 0 88 56 40 152 120 128 200 1920 8 233 8 0 8 8 8 0 0 0 0 16 24 88 64 8 32 40 2048 8 77 0 0 8 8 0 8 8 0 0 64 136 160 48 192 24 120 2304 8 1631 0 0 8 0 8 0 8 8 0 24 80 40 16 96 64 32 2560 8 2249 0 0 8 0 8 0 8 8 0 8 72 40 88 48 32 96 2816 8 1235 8 8 0 0 0 8 0 8 0 16 88 96 56 24 48 64 3072 8 671 0 0 8 0 8 0 8 8 0 8 48 32 64 88 40 56 3328 8 1459 0 0 8 0 8 0 8 8 0 32 8 56 80 16 72 48 3568 8 147 0 0 8 0 8 0 8 8 0 72 64 48 88 8 184 248 3840 8 3721 8 0 8 8 8 0 0 0 0 16 48 24 8 32 40 88 4096 8 83 8 8 0 0 0 8 8 0 0 16 120 152 24 216 64 240 4608 8 181 0 8 0 8 0 8 8 0 0 32 176 216 136 64 224 248 5120 8 3629 0 8 0 8 8 0 8 0 0 16 40 96 88 80 32 48 5632 8 211 0 0 8 0 8 0 8 8 0 24 208 112 224 168 184 48 6144 8 4355 8 0 8 8 8 0 0 0 0 8 16 64 24 48 80 32 Заметим, что в таблице вектора размывания α (и аналогично β) записаны так, что крайнее левое значение соответствует α(0) (и аналогично β(0))

Свойства перемежителя ARP

Существует несколько способов для изменения таблицы перемежителя. Например, с использованием набора параметров ARP, которые относятся к нескольким размерам перемежителя, можно уменьшить память. Например, 1024-битовые, 2048-битовые, 4096-битовые перемежители, все могут использовать идентичные параметры ARP. В еще одном варианте, если требуется, некоторые из строк таблицы могут быть перепроектированы на основе различных значений C. В другом расширении некоторые из записей параметров (например, α(0) и β(0)) могут быть фиксированными (например, всегда нулем).

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

1. Значение смещения A=3 выбрано для уменьшения памяти.

2. На основе исследования производительности и памяти длина цикла C=4 используется для K'<1024, C=8 для K'≥1024.

3. Для каждого размера блока было выполнено моделирование, чтобы удостовериться, что производительность перемежителя ARP (с циклически замкнутым (tail-biting) кодированием) близка к производительности с перемежителем, определенным в спецификации для турбокода 3GPP, или лучше ее.

4. Таблица 1 была определена на основе (5) для охвата определенного набора размеров перемежителя (например, 128-6144 битов). Если предпочтительно, то могут быть удалены или добавлены другие размеры перемежителя.

5. Все перемежители, определенные в 105, могут использоваться для турбокодов с концевой комбинацией битов или циклически замкнутых (tail-biting) турбокодов, в зависимости от допустимого ухудшения производительности.

Фиг.3 является блок-схемой приемника 300. На входе схема 302 обработки заполнителя принимает вектор сигнала, который мог быть передан по беспроводной связи. После этого схема 306 определяет размер K' перемежителя, что может быть выполнено способом, аналогичным способу, рассмотренному выше, например, посредством поиска в таблице из памяти 308, или посредством таких вычислений, как (7), (8) и (2). Следовательно, с учетом размера K блока информации декодер 304 использует размер K' перемежителя, идентичный тому, который использовался кодером 101. Схема 302 обработки заполнителя используется для надлежащей обработки принятого вектора сигнала и позиций битов-заполнителей (например, если позиции бита-заполнителя известны, то во время декодирования соответствующие величины LLR могут быть установлены на очень высоком (уровне)). После этого турбодекодер 304 выполняет декодирование и получает оценку û входного блока длины K'. Наконец, схема 310 извлечения блока информации извлекает оцененный блок информации из û. Хотя схема 302 обработки заполнителя изображена вне турбодекодера для простоты объяснения, при реализации они обе могут быть объединены.

Фиг.4 является блок-схемой турбодекодера по фиг.3. Как изображено, перемежитель 402 и деперемежитель 401 находятся между схемой 403 декодирования и схемой 404 декодирования. Как известно в данной области техники, выполняется итеративное декодирование, однако, в отличие от декодеров известного уровня техники, размер K' перемежителя связан с K", где K" - из набора размеров, причем набор размеров содержит K" = a^p × f, p_min ≤ p ≤ p_max, f_min ≤ f ≤ f_max, где a - целое число, f - постоянное целое число между f_min и f_max, и p принимает целочисленные значения между p_min и p_max, a>1, p_max> p_min, p_min> 1.

Как обсуждалось выше, в одном варианте осуществления K' = K". В еще одном варианте осуществления K' = K", когда K" не является числом, кратным (2^m-l), иначе с использованием K' = K" + δ (K"), когда K" является числом, кратным (2^m-l), где m - длина памяти компонентного сверточного кодера и δ(K") - небольшое положительное или отрицательное целое число, не равное числу, кратному (2^m-l). В одном варианте осуществления m=3.

Перемежитель 402 использует перестановку π(i) = (iP₀+A+d(i)) mod K', где 0 ≤ i ≤ K'-1 является порядковым индексом позиций символа после перемежения, π(i) - индекс символа до перемежения, соответствующий позиции i, K' - размер перемежителя в символах, P₀ - число, которое является взаимно простым с K', A - константа, C - небольшое число, на которое делится K', и d(i) - вектор размывания вида d(i) = α(i mod C) + P₀ × β(i mod C), где α(·) и β (·) - векторы, каждый длины C, периодически используемые для 0 ≤ i ≤ K'-1. Значения K', C, P₀, α(·) и β(·) предпочтительно взяты из строки таблицы 1.

Фиг.5 является блок-схемой, изображающей работу передатчика 100. Логический поток начинается с этапа 501, где схема 103 определяет размер K' перемежителя, который связан с K", где K" - из набора размеров, причем набор размеров содержит K" = a^p x f, p_min ≤ p ≤ p_max, f_min ≤ f ≤ f_max, где a - целое число, f - постоянное целое число между f_min и f_max, и p принимает целочисленные значения между p_min и p_max, a>1, p_max> p_min, p_min> 1. Как обсуждалось выше, в одном варианте осуществления K' = K". В еще одном варианте осуществления K' = K", когда K" не является числом, кратным (2^m-l), иначе с использованием K' =K" + δ (K"), когда K" является числом, кратным (2^m-l), где m - длина памяти компонентного сверточного кодера и δ(K") - небольшое положительное или отрицательное целое число, не равное числу, кратному (2^m-l). В одном варианте осуществления m=3.

На этапе 503 схема 109 вставки заполнителя принимает блок информации размера K и вставляет этот блок информации размера K во входной блок u размера K' и выводит этот входной блок u. После этого перемежитель 201 перемежает входной блок размера K' (этап 507) (предпочтительно с использованием бесконфликтного перемежителя) и отправляет перемеженный блок размера K' в схему 203 кодирования (этап 509). Наконец, на этапе 511, исходный входной блок и перемеженный входной блок кодируются.

Как обсуждалось выше, этап перемежения входного блока содержит этап использования перестановки π(i) = (iP₀ + A + d(i)) mod K', где 0 ≤ i ≤ K'-l является порядковым индексом позиций бита после перемежения, π(i) - индекс бита до перемежения, соответствующий позиции i, K' - размер перемежителя в битах, P₀ - число, которое является взаимно простым с K', A - константа, C - небольшое число, на которое делится K', и d(i) - вектор размывания вида d(i) = α(i mod C) + P₀ × β(i mod C), где α(·) и β(·) - векторы, каждый длины C, периодически используемые для 0 ≤ i ≤ K'-1. Значения K', C, P₀, α(·) и β(·) предпочтительно взяты из таблицы 1.

Фиг.6 является блок-схемой, изображающей работу приемника по фиг.3. Логический поток начинается на этапе 601, где схема 302 определяет размер K' перемежителя. На этапе 603 схема 302 добавляет информацию бита-заполнителя к принятому вектору сигнала, например, если биты-заполнители и позиции бита-заполнителя известны, схема 302 может установить на высоком уровне величину логарифмического отношения правдоподобия (LLR) этих позиций на входе турбодекодера. На этапе 605 турбодекодер декодирует входной блок с использованием перемежителя и деперемежителя размера K' и выводит оценку входного блока длины K'. На этапе 607 схема 310 извлечения блока информации удаляет биты-заполнители для получения оценки блока информации длины K.

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

Изобретение относится к кодированию и декодированию данных, в частности к способу и устройству для выбора размеров перемежителя для турбокодов. Во время работы принимается блок информации размера K. Определяется размер K' перемежителя, который связан с K'', где K'' - из набора размеров, причем этот набор размеров содержит K''=a^p×f, p_min≤p≤p_max, f_min≤f≤f_max, где а - целое число, и f - постоянное целое число между f_min и f_max, р принимает целочисленные значения между p_min и p_max, a>1, p_max>p_min, p_min>1. Во входной блок размера K' вставляется блок информации размера K с использованием битов-заполнителей, если требуется. С использованием исходного входного блока и перемеженного входного блока выполняется кодирование с использованием турбокодера для получения блока кодового слова. Этот блок кодового слова передается через канал. Технический результат - обеспечение высокого уровня параллельной обработки без конфликтов при обращении к памяти турбоперемежителя. 2 н. и 7 з.п. ф-лы, 6 ил., 1 табл.

1. Способ работы турбокодера, содержащий этапы, на которых:
принимают блок информации размера K,
определяют размер K' перемежителя, который связан с K”, где K” - из набора размеров, причем набор размеров содержит K”=a^p×f, p_min≤p≤p_max, f_min≤f≤f_max, где а - целое число, f - постоянное целое число между f_min и f_max и р принимает целочисленные значения между p_min и p_max, а>1, p_max>p_min, p_min>1,
вставляют блок информации размера K во входной блок размера K' и
перемежают входной блок с использованием перемежителя размера K',
кодируют исходный входной блок и перемеженный входной блок для получения блока кодового слова и
передают блок кодового слова через канал,
причем этап опеделения размера K' перемежителя, который связан с K”, содержит использование K'=K”.

2. Способ по п.1, в котором этап определения размера K' перемежителя, который связан с K”, содержит этап, на котором используют K'=K”, когда K” не является числом, кратным (2^m-1), иначе используют K'=K”+δ(K”), когда K” является числом, кратным (2^m-1), где m - длина памяти компонентного сверточного кодера и δ(K”) - небольшое положительное или отрицательное целое число, не равное числу, кратному (2^m-1).

3. Способ по п.2, в котором m=3.

4. Способ по п.1, в котором f_max=a×f_min-1.

5. Способ по п.1, в котором f_max=a×(f_min-1).

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

7. Способ по п.1, в котором этап перемежения входного блока содержит этап, на котором используют перестановку π(i)=(iP₀+А+d(i)) mod K', где 0≤i≤K'-1 является порядковым индексом позиций символа после перемежения, π(i) - индекс символа до перемежения, соответствующий позиции i, K' - размер перемежителя в символах, Р₀ - число, которое является взаимно простым с K', А - константа, С - небольшое число, на которое делится K', и d(i) - вектор размывания вида d(i)=α(i mod С)+Р₀×β(i mod С), где α(·) и β(·) - векторы, каждый длиной С, периодически используемые для 0≤i≤K'-1.

8. Способ по п.7, в котором значения K', С, Р₀, α(·) и β(·) взяты, по меньшей мере, из одной строки следующей таблицы:
Размер K' перемежителя C Р₀ α β 128 4 81 4 0 0 4         0 20 120 68         144 4 91 4 0 4 0         0 76 20 52         160 4 123 4 4 0 0         0 4 8 12         176 4 127 4 4 0 0         0 12 112 44         192 4 169 4 0 4 0         0 8 4 16         208 4 37 4 0 4 0         0 68 20 164         216 4 121 4 4 0 0         0 68 12 28         240 4 161 0 0 4 4         0 16 196 212         256 4 31 0 0 4 4         0 60 8 68         288 4 131 0 4 0 4         0 80 144 36         320 4 69 0 0 4 4         0 4 8 12           352 4 35 4 0 0 4         0 48 96 152         384 4 91 0 0 4 4         0 4 20 24         416 4 31 4 4 0 0         0 24 28 60         440 4 53 0 4 4 0         0 4 20 216         480 4 53 0 4 4 0         0 72 192 12         512 4 273 0 0 4 4         0 20 8 24         576 4 29 0 0 4 4         0 64 120 68         640 4 147 0 0 4 4         0 24 12 4         704 4 309 0 0 4 4         0 4 12 8         768 4 241 0 0 4 4         0 4 12 8         832 4 53 0 0 4 4         0 4 12 8         888 7 77 0 4 4 0         0 48 64 140         960 4 143 0 0 4 4         0 4 12 8         1024 8 245 8 0 8 8 0 0 8 0 0 8 40 16 96 80 56 88 1152 8 119 0 0 8 0 8 0 8 8 0 8 40 64 80 48 24 88 1280 8 897 0 0 8 0 8 0 8 8 0 8 96 88 32 16 48 40 1408 8 593 0 8 0 8 8 0 8 0 0 8 96 48 32 16 80 40 1536 8 1139 0 0 8 0 8 0 8 8 0 16 56 88 80 24 72 64 1664 8 1451 0 8 0 8 8 0 8 0 0 16 40 96 88 80 32 48 1776 8 115 8 0 0 0 0 8 8 8 0 88 56 40 152 120 128 200 1920 8 233 8 0 8 8 8 0 0 0 0 16 24 88 64 8 32 40 2048 8 77 0 0 8 8 0 8 8 0 0 64 136 160 48 192 24 120 2304 8 1631 0 0 8 0 8 0 8 8 0 24 80 40 16 96 64 32 2560 8 2249 0 0 8 0 8 0 8 8 0 8 72 40 88 48 32 96 2816 8 1235 8 8 0 0 0 8 0 8 0 16 88 96 56 24 48 64 3072 8 671 0 0 8 0 8 0 8 8 0 8 48 32 64 88 40 56 3328 8 1459 0 0 8 0 8 0 8 8 0 32 8 56 80 16 72 48 3568 8 147 0 0 8 0 8 0 8 8 0 72 64 48 88 8 184 248 3840 8 3721 8 0 8 8 8 0 0 0 0 16 48 24 8 32 40 88 4096 8 83 8 8 0 0 0 8 8 0 0 16 120 152 24 216 64 240 4608 8 181 0 8 0 8 0 8 8 0 0 32 176 216 136 64 224 248 5120 8 3629 0 8 0 8 8 0 8 0 0 16 40 96 88 80 32 48 5632 8 211 0 0 8 0 8 0 8 8 0 24 208 112 224 168 184 48 6144 8 4355 8 0 8 8 8 0 0 0 0 8 16 64 24 48 80 32

9. Устройство для работы турбокодера, содержащее:
приемную схему, которая принимает входной блок размера K', и
кодер, который кодирует входной блок с использованием перемежителя размера K' и перестановки π(i)=(iP₀+A+d(i)) mod K', где 0≤i≤K'-1 является порядковым индексом позиций бита после перемежения, π(i) - индекс бита до перемежения, соответствующий позиции i, Р₀ - число, которое является взаимно простым с K', А - константа, равная 3, С - небольшое число, на которое делится K', и d(i) - вектор размывания вида d(i)=-α(i mod С)+Р₀×β(i mod С), где α(·) и β(·) - векторы, каждый длиной С, периодически используемые для 0≤i≤K'-1, и причем значения K', С, Р₀, α(·) и β(·) взяты, по меньшей мере, из одной строки следующей таблицы:
Размер K' перемежителя C P₀ α β 128 4 81 4 0 0 4         0 20 120 68         144 4 91 4 0 4 0         0 76 20 52         160 4 123 4 4 0 0         0 4 8 12         176 4 127 4 4 0 0         0 12 112 44         192 4 169 4 0 4 0         0 8 4 16         208 4 37 4 0 4 0         0 68 20 164         216 4 121 4 4 0 0         0 68 12 28         240 4 161 0 0 4 4         0 16 196 212         256 4 31 0 0 4 4         0 60 8 68         288 4 131 0 4 0 4         0 80 144 36         320 4 69 0 0 4 4         0 4 8 12         352 4 35 4 0 0 4         0 48 96 152         384 4 91 0 0 4 4         0 4 20 24         416 4 31 4 4 0 0         0 24 28 60         440 4 53 0 4 4 0         0 4 20 216         480 4 53 0 4 4 0         0 72 192 12         512 4 273 0 0 4 4         0 20 8 24         576 4 29 0 0 4 4         0 64 120 68         640 4 147 0 0 4 4         0 24 12 4         704 4 309 0 0 4 4         0 4 12 8         768 4 241 0 0 4 4         0 4 12 8         832 4 53 0 0 4 4         0 4 12 8         888 7 77 0 4 4 0         0 48 64 140         960 4 143 0 0 4 4         0 4 12 8         1024 8 245 8 0 8 8 0 0 8 0 0 8 40 16 96 80 56 88 1152 8 119 0 0 8 0 8 0 8 8 0 8 40 64 80 48 24 88 1280 8 897 0 0 8 0 8 0 8 8 0 8 96 88 32 16 48 40 1408 8 593 0 8 0 8 8 0 8 0 0 8 96 48 32 16 80 40 1536 8 1139 0 0 8 0 8 0 8 8 0 16 56 88 80 24 72 64 1664 8 1451 0 8 0 8 8 0 8 0 0 16 40 96 88 80 32 48 1776 8 115 8 0 0 0 0 8 8 8 0 88 56 40 152 120 128 200 1920 8 233 8 0 8 8 8 0 0 0 0 16 24 88 64 8 32 40 2048 8 77 0 0 8 8 0 8 8 0 0 64 136 160 48 192 24 120 2304 8 1631 0 0 8 0 8 0 8 8 0 24 80 40 16 96 64 32 2560 8 2249 0 0 8 0 8 0 8 8 0 8 72 40 88 48 32 96 2816 8 1235 8 8 0 0 0 8 0 8 0 16 88 96 56 24 48 64 3072 8 671 0 0 8 0 8 0 8 8 0 8 48 32 64 88 40 56 3328 8 1459 0 0 8 0 8 0 8 8 0 32 8 56 80 16 72 48 3568 8 147 0 0 8 0 8 0 8 8 0 72 64 48 88 8 184 248 3840 8 3721 8 0 8 8 8 0 0 0 0 16 48 24 8 32 40 88 4096 8 83 8 8 0 0 0 8 8 0 0 16 120 152 24 216 64 240 4608 8 181 0 8 0 8 0 8 8 0 0 32 176 216 136 64 224 248 5120 8 3629 0 8 0 8 8 0 8 0 0 16 40 96 88 80 32 48 5632 8 211 0 0 8 0 8 0 8 8 0 24 208 112 224 168 184 48 6144 8 4355 8 0 8 8 8 0 0 0 0 8 16 64 24 48 80 32