СПОСОБ И УСТРОЙСТВО КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ДАННЫХ
METHOD AND DEVICE TO CODE AND DECODE DATA

Область техники, к которой относится изобретение
Настоящее изобретение относится, в основном, к кодированию и декодированию данных, в частности к способу и устройству турбокодирования и турбодекодирования.
Уровень техники
Передачи цифровых данных по проводным и беспроводным линиям связи могут искажаться, например, шумом в линии связи или канале, помехой от других передач или других окружающих факторов. Для борьбы с ошибками, вводимыми каналом, многие системы связи применяют методы коррекции ошибок, способствующие выполнению связи.
u
x
y
u
K
N
N
Одним методом, используемым для коррекции ошибок, является турбокодирование информационного блока, перед тем как он будет передан по каналу. Используя такой метод, кодер в передатчике системы связи кодирует входной блок  длины ' битов в блок  кодового слова из  битов. Блок кодового слова затем передается по каналу, возможно после дополнительной обработки, такой как канальное перемежение, как определено в спецификациях Института инженеров по электротехнике и радиоэлектронике IEEE 802 16е. В приемнике турбодекодер принимает вектор  принятого сигнала длины  в качестве входа и генерирует оценку  вектора .
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
f, p
p
p
f
f
f
a
f
f
f
p
p
p
a
p
p
p
K
K
K
p
min
max
min
max
min
max
min
max
max
min
min
Во время работы принимается информационный блок размера . Определяется размер  перемежителя, где ' связан с ”, где  из набора размеров; причем набор размеров содержит ”=×≤≤; ≤≤, где  представляет собой целое число,  представляет собой постоянное целое число между  и , и  принимает целочисленные значения между  и , >1, >, >1. Информационный блок размера  заполняется во входной блок размера '. Входной блок перемежается с использованием перемежителя размера '. Исходный входной блок и перемеженный входной блок кодируются для получения блока кодового слова. Блок кодового слова передается по каналу.
K
K
K
K
В другом варианте осуществления настоящего изобретения этап определения размера ' перемежителя, который связан с ”, содержит этап использования '=”.
K
K
K
K
K
K
K
K
K
m
K
m
m
m
m
В еще другом варианте осуществления настоящего изобретения этап определения размера ' перемежителя, который связан с ”, содержит этап использования '=”, когда ” не является кратным (2-1); в противном случае, использования '=”+δ(”), когда ” является кратным (2-1), причем  представляет собой емкость памяти составного сверточного кодера, и δ(”) представляет собой небольшое положительное или отрицательное целое число, не равное кратному (2-1). В одном варианте осуществления =3.
π
i
iP
A
d
i
K
i
K
π
i
i
K
P
K
А
С
K
d
i
d
i
β
i
C
P
α
i
C
С
i
K
0
0
0
В еще другом варианте осуществления настоящего изобретения этап перемежения входного блока содержит этап использования перестановки ()=(++())mod', где 0≤≤'-1 представляет собой последовательный индекс положений символа после перемежения, () представляет собой индекс символа перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в символах,  представляет собой число, которое является относительно простым для ',  представляет собой постоянную, представляет собой небольшое число, которое делит ', и () представляет собой вектор возмущения вида ()=(mod)+×(mod), где α(·) и β(·) представляют собой векторы, каждый длиной , периодически применяемый для 0≤≤'-1.
π
i
f
i
f
i
K
i
K
π
i
i
K
f
f
1
2
1
2
2
В еще другом варианте осуществления настоящего изобретения этап перемежения входного блока содержит этап использования перестановки ()=(×+×)mod', где 0≤≤'-1 представляет собой последовательный индекс положений символа после перемежения, () представляет собой индекс символа перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в символах, и  и  представляют собой коэффициенты, определяющие перемежитель.
Перед описанием кодирования и декодирования данных предоставляются следующие определения, чтобы установить необходимые основные принципы.
K
-  обозначает размер информационного блока.
K
- ' обозначает размер перемежителя (т.е. размер входного блока, для которого определяется перемежитель турбокода).
K
- ” обозначает вспомогательную переменную, которая может использоваться при определении размера перемежителя.
K
filler
-  обозначает количество битов заполнителя, добавляемых к информационному блоку.
- π обозначает внутренний перемежитель турбокода.
x
x
- Операция определения нижнего значения  обозначает наибольшее целое число, которое меньше или равно , и операция определения верхнего значения  обозначает наименьшее целое число, которое больше или равно .
u
K
K
-  обозначает входной блок, который имеет длину ' и который посылается на турбокодер в передатчике.  обозначает оцененный входной блок, который имеет длину ' и который создается турбодекодером в приемнике. Отметьте, что , когда нет ошибки декодирования. В противном случае, .
K
K
K
K
a
f,
p
p
p
f
f
f
a
f
f
f
p
p
p
a
p
p
p
p
min
max
min
max
min
max
min
max
max
min
min
Обратимся теперь к чертежам, на которых подобные позиции обозначают подобные компоненты, фиг.1 представляет собой блок-схему передатчика 100. Как показано, передатчик 100 содержит схему 109 вставки заполнителя, турбокодер 101, схему 103 определения размера перемежителя, таблицу 105 параметров перемежителя и передатчик 107. Кодер 101, предпочтительно, представляет собой турбокодер Проекта партнерства по созданию системы 3-го поколения (3GPP) со скоростью 1/3, однако, методы, описанные в данном документе для работы кодера 101, могут быть применены к другим кодерам, включая, но не ограничиваясь турбокодерами, выполняющими турбокодирование с хвостовыми битами или без хвостовых битов, циклически замкнутыми, бинарными или дуобинарными турбокодерами, турбокодерами, использующими различные методы согласования скорости и выкалывания, и т.д. Схема 103 определяет размер ' перемежителя, который связан с ”, где ” из набора размеров; причем набор размеров содержит ”=×≤≤; ≤≤, причем  представляет собой целое число,  представляет собой постоянное целое число между  и , и  принимает целые значения между  и  , >1, >, >1.
K
K
K
K
K
K
K
K
filler
Во время работы передатчика 100 информационный блок размера  должен кодироваться турбокодером 101. Для некоторых систем связи, где используется большое количество различных , является неэффективным (и часто невозможным) определение бесконфликтного (CF) перемежителя для каждого размера  информационного блока. Является предпочтительным, если малый набор (') хорошо сконструированных CF-перемежителей может охватывать все размеры информационных блоков. При заданном размере  информационного блока подходящий размер ' перемежителя может быть выбран схемой 103 из набора доступных размеров (например, размеров перемежителя, перечисленных в таблице 105). Информационный блок затем заполняется во входной блок размера ' посредством схемы 109 и посылается в качестве входа на турбокодер 101. Типовым размещением является заполнение информационного блока  битами заполнителя (при помощи схемы 109 вставки заполнителя). Отметьте, что термины «размер» и «длина» используются попеременно для указания количества элементов в блоке или векторе.
K
π
i
iP
A
d
i
K
i
K
π
i
i
K
P
K
А
С
K
d
i
d
i
β
i
C
P
α
i
C
C
i
K
π
i
f
i
f
i
K
i
K
π
i
i
K
f
f
0
0
0
1
2
1
2
2
Если ' выбрано схемой 103, оно подается на турбокодер 101. Во время кодирования может использоваться бесконфликтный перемежитель (не показан на фиг.1). Например, перемежитель может использовать перестановку ()=(++())mod', причем 0≤≤'-1 представляет собой последовательный индекс положений символа после перемежения, () представляет собой индекс символа перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в символах,  представляет собой число, которое является относительно простым для ',  представляет собой постоянную, представляет собой небольшое число, которое делит ', и () представляет собой вектор «возмущения» вида ()=(mod)+×(mod), где α(·) и β(·) представляют собой векторы, каждый длиной , периодически применяемый для 0≤≤'-1. В качестве другого примера, перемежитель может использовать перестановку ()=(×+×)mod', где 0≤≤'-1 представляет собой последовательный индекс положений символа после перемежения, () представляет собой индекс символа перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в символах, и  и  представляют собой коэффициенты, определяющие перемежитель. Как правило, символ может состоять из многочисленных битов, и этап перемежения может использовать дополнительный этап перестановки битов в символе. Без потери общности, обсуждение ниже рассматривает типовой случай, где символ состоит только из одного бита (таким образом, нет необходимости переставлять биты в символе), и термины «бит» и «символ» могут использоваться попеременно.
x
x
x
Выходной результат турбокодера 101 содержит блок  кодового слова, и  посылается на передатчик 107, где он передается по каналу. Передатчик может выполнять дополнительную обработку, такую как согласование скоростей, канальное перемежение, модуляция и т.д. перед передачей блока  кодового слова по каналу.
R
N
N
N
TB
TB
TB
Фиг.2 представляет собой блок-схему кодера 101 по фиг.1. Как показано, кодер 101 содержит перемежитель 201, схему 202 кодирования и схему 203 кодирования. Пример кодера представляет собой турбокодер, определенный в спецификации 3GPP. Исходная скорость кодирования турбокодера, определенного в 3GPP, имеет присущую данной системе скорость кодирования =1/3. На выходе турбокодера три бита создаются для каждого бита во входном блоке: один систематический бит (равный биту во входном блоке), один бит контроля четности от составного кодера 1, один бит контроля четности от составного кодера 2. Кроме того, выходной результат турбокодера также может включать в себя  хвостовых битов, которые используются для завершения решетки составных кодов. Например, для турбокода 3GPP =12 битов на выходе турбокодера, 6 хвостовых битов на составной код. С другой стороны, можно использовать циклически замкнутые составные сверточные коды, таким образом делая =0.
π
i
i
K
бесконфликтным
W
-1
Перемежителем 201 может быть бесконфликтный перемежитель. Перемежитель (), 0≤≤', например, является  для размера  окна, если и только если он удовлетворяет следующему ограничению как для ψ=π (перемежитель), так и для ψ=π (деперемежитель),
(1),
j
W
t
M
K
W
t
M
K
MW
M
где 0≤<, 0≤; ν<(='/) и ≠ν. Хотя это не всегда необходимо, для эффективной конструкции турбодекодера обычно все  окон заполнены, где '=. Члены в (1) представляют собой адреса банка памяти, по которым одновременно обращаются  процессоров при записи косвенных значений в выходные банки памяти во время итеративного декодирования. Если все эти адреса банка памяти являются уникальными в течение каждой операции считывания и записи, то нет конфликтов при обращении к памяти и, следовательно, может быть исключена задержка перемежения (деперемежения), приводя к высокоскоростной реализации декодера.
K
K
Во время работы турбокодера 101 входной блок длиной ' битов поступает как на перемежитель 201, так и на схему 202 кодирования. Перемежителем 201 может быть бесконфликтный перемежитель размера '.
x
x
Перемежитель 201 перемежает входной блок и пропускает входной блок в перемеженном порядке на схему 203 кодирования. Схема 203 кодирования затем кодирует перемеженный входной блок. Аналогичным образом, схема 202 кодирования кодирует исходный входной блок. Блок  кодового слова состоит из систематического блока (равного входному блоку), выходного результата схемы 202 кодирования и выходного результата схемы 203 кодирования. Блок  кодового слова затем посылается на передатчик 107, который также может непосредственно принимать копию входного блока.
В качестве примера бесконфликтного перемежителя, перемежитель с почти регулярной перестановкой (ARP) определяется следующим выражением:
π
i
iP
A
d
i
K
0
()=(++())mod',
i
K
π
i
i
K
P
K
А
С
K
d
i
d
i
β
i
C
P
α
i
C
С
i
K
C
π
C
0
0
где 0≤≤'-1 представляет собой последовательный индекс положений бита после перемежения, () представляет собой индекс бита перед перемежением, соответствующий положению , ' представляет собой размер перемежителя,  представляет собой число, которое является относительно простым для ',  представляет собой постоянную,  представляет собой небольшое число, которое делит ', и () представляет собой вектор возмущения вида ()=(mod)+×(mod), где α(·) и β(·) представляют собой векторы, каждый длиной , периодически применяемые для 0≤≤'-1. Как α(·), так и β(·) состоят из кратных . Общий перемежитель (·), составленный таким образом, имеет квазициклические (т.е. периодические) свойства с периодом , и при использовании циклически замкнутых турбокодов сам турбокод становится квазициклическим, приводя к упрощенной процедуре конструирования кода.
π
i
f
i
f
i
K
i
K
π
i
i
K
f
f
1
2
1
2
2
В качестве другого примера бесконфликтного перемежителя, перемежитель с перестановкой с использованием квадратного многочлена (QPP) определяется следующим выражением ()=(×+×)mod', где 0≤≤'-1 представляет собой последовательный индекс положений символа после перемежения, () представляет собой индекс символа перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в символах, и  и  представляют собой коэффициенты, определяющие перемежитель. Подобно перемежителям ARP турбокод также является квазициклическим, если он циклически замкнутый.
M
M
K
K
W
W
C
K
K
K
M
M
Если перемежитель 201 может удовлетворять (1) различным значениям , тогда декодер может быть реализован с использованием различных степеней параллельности (один для каждого ). Таким образом, желательно выбрать ', который имеет различные коэффициенты. Для перемежителя ARP длины ' может использоваться любой размер  окна, где  представляет собой кратное  и коэффициента ', для высокоскоростного декодирования без конфликтов при обращении к памяти. С различным определением параллельных окон можно использовать любой коэффициент  в качестве числа параллельных окон. Для перемежителя QPP любой коэффициент размера ' перемежителя представляет собой возможный уровень параллельности . Это обеспечивает гибкость и масштабируемость конструкции декодера, допуская широкий диапазон коэффициентов  параллельности. Таким образом, хороший компромисс между скоростью декодирования и сложностью может быть достигнут на основе требований к системе (или классам пользовательских элементов).
K
Выбор размера ' перемежителя
K
K
K
K
Как описано выше, схема 103 определения размера перемежителя должна определять размер ' перемежителя для данного . Этот раздел описывает путь выбора ограниченного количества размеров (т.е. '), для которых перемежители турбокода могут быть определены. Как указано ранее, схема вставки заполнителя (вместе со способами выкалывания или согласования скорости) может использоваться для обработки любого размера  информационного блока. Как правило, выбор размера перемежителя должен принимать во внимание нагрузку декодирования и ухудшение рабочих характеристик из-за битов заполнителя.
K
K
K
K
K
K
K
K
K
K
K
K
filler
filler
Желательно, чтобы количество битов  заполнителя, добавляемых к информационному блоку для формирования входного блока, ограничивалось небольшим процентом (например, примерно 10-13%) от размера  информационного блока. Это достигается посредством ограничения разности между соседними размерами перемежителя, т.е. соседними значениями ' (предполагая, что все доступные значения ' хранятся в возрастающем порядке). Количество битов заполнителя минимизируется посредством выбора наименьшего доступного ', так что '≥. Количество битов заполнителя равно ='-. Однако также могут быть выбраны другие доступные значения '≥, если потребуется.
K
K
min
max
Рассмотрим следующий набор размеров, определенный для охвата размеров информации между  и .
K"=a
×f
P
≤P≤P
f
≤f≤f
p
min
max
min
max
, ,  (2),
a
f
f
f
p
p
p
a
p
p
p
полулогарифмическое расслоение
K
K
K
K
min
max
min
max
max
min
min
где  представляет собой целое число,  представляет собой постоянное целое число между  и , и  принимает целые значения между  и , >1, >, >1. Хотя это и не является обязательным, можно выбрать эти параметры, так что  и  в тоже время отбрасывая любые размеры, которые могут быть необязательными. Этот способ выбора ограниченного набора размеров для охвата диапазона размеров информационного блока упоминается как . Для данного информационного блока размера  размер ' связан с ”, основанном на таблице полулогарифмического расслоения, и размером  входного блока.
Полулогарифмическое расслоение подобно операции сжатия, применяемой при сжатии сигналов с большим динамическим диапазоном, например, компандеры по А-закону и мю-закону, используемые в речевых кодеках. Правило полулогарифмического расслоения позволяет эффективной конструкции охватывать большой диапазон размеров информационного блока.
f
f
K
p
a
f
a
f
min
max
max
min
p
p+1
Из нескольких путей выбора параметров одним путем выбора значений  и  является выравнивание значений ”, вытекающих из , друг с другом, т.е. ×(+1)=×, таким образом
f
=a×f
-1
max
min
.
p
K
a
a
K
p
K
K
K
K
p
f
K
K
p
f
p
p
filler
min
min
Для данного значения  разделение между двумя соседними размерами ” блоков определяется посредством , которое означает, что добавляется максимум -1 битов заполнителя, если размер  информационного блока находится в группе , и размер перемежителя равен ”. Таким образом, доля битов  заполнителя относительно размера  информационного блока ограничивается так, как показано ниже, что происходит тогда, когда размер  блока несколько больше размера, определяемого посредством (, ), и, используя '=”, определяемого посредством (, +1), следующим:
K
p
a
f
a
f
f
a
f
K
K
f
p
p+1
max
min
max
min
filler
min
Альтернативно, значения ”, вытекающие из соседнего , могут выравниваться друг с другом посредством ×=×(-1), приводя к =×(-1). Это даст аналогичную границу /. Поэтому параметры для полулогарифмического расслоения могут быть настроены в соответствии с диапазоном поддерживаемых размеров блока и также по допустимой доли битов заполнителя. Выбор  требует равновесия между следующими двумя требованиями:
f
min
-  должна быть большой, чтобы уменьшить долю битов заполнителя;
f
p
f
f
a
f
f
a
f
min
max
min
min
max
min
-  должна быть малой, чтобы ограничивать размер таблицы перемежителя, так как количество размеров блока, определенных для каждого , равно -+1=(-1)×, предполагая, что =×-1.
K
K
K
K
Способ полулогарифмического расслоения является очень простым в том, что для любого размера блока подлежащий использованию размер ' перемежителя может легко определяться на основе ”, вычисленного из (2). Если размеры полулогарифмического расслоения определены (”), размер ' перемежителя может быть получен из размеров полулогарифмического расслоения (без существенного отклонения) посредством, например:
K
K
1. Используя '=”. Другими словами, размеры полулогарифмического расслоения могут непосредственно использоваться в качестве действительных размеров перемежителя.
K
K
K
K
K
K
K
m
K
m
m
m
m
m
m
m
m
2. Используя '=”, когда ” не является кратным (2-1), в противном случае, используя '=”+δ(”), когда ” является кратным (2-1), причем  является емкостью памяти составного сверточного кодера, и δ(”) представляет собой небольшое положительное или отрицательное целое число, не равное кратному (2-1). Это полезно, если составные сверточные коды являются циклически замкнутыми, где кратные (2-1) являются недопустимыми. Размеры, определенные по способу полулогарифмического расслоения по (2), иногда могут включать в себя размеры, которые являются неподходящими размерами перемежителя для турбокодирования. Например, циклически замкнутая версия турбокодера 3GPP с восемью состояниями (=3) не поддерживает размеры входного блока (т.е. размеры перемежителя), которые являются кратными 7 (т.е. 2-1). В таких случаях, всякий раз, когда уравнение (2) приводит к размеру, который является кратным 2-1, малое значение вычитается или добавляется к нему, так что результирующий размер больше не является кратным 2-1.
a
f
f
K
K
K
K
K
K
K
K
K
K
min
max
p
Например, если =2, =8 и =15, тогда размеры перемежителя вида '=”=2×14 являются кратными 7, и, следовательно, являются недействительными размерами перемежителя при использовании циклически замкнутого турбокода (TC) 3GPP. Поэтому этот случай должен обрабатываться с небольшим изменением, например, используя '=”, когда ” не является кратным 7; в противном случае, используя '=”+δ(”), когда ” является кратным 7, и δ(”) является малым положительным или отрицательным целым числом, не равным кратному 7.
K
K
d
C
K
d
d
C
K
C
Для размеров ”, которые являются недействительным выбором для циклически замкнутых перемежителей, одним простым путем определения связанного размера ' перемежителя является посредством вычитания (добавление также допустимо) × из ”, где  представляет собой малое положительное целое число, и  не является кратным 7. Для перемежителя ARP  может быть длиной цикла перемежителя ARP, используемой для размеров блока, близких к ', в наборе доступных размеров. (Вспомните, что размер блока перемежителя ARP представляет собой кратное длин  цикла.) Другими словами,
K
K
dC
'=”- (3)
или
K
K
dC
'=”+ (4),
K
C
K
K
C
K
где ” является кратным 7. Так как  обычно представляет собой четное целое число, такое как 4, 8, 12 или 16, эта подстройка дает два преимущества, а именно, (а) ' не является кратным 7, и (b) ' является кратным  и, следовательно, может быть разработан перемежитель ARP для размера '.
d
K
d
Для простоты, один и тот же  может выбираться для всех ”, которые необходимо подстраивать. Одним важным моментом для выбора  является то, что он должен быть таким, чтобы все размеры, полученные посредством (3) или (4), имели значительное количество коэффициентов, которые позволяют поддерживать широкий диапазон параллельности для CF-перемежителя, определенного таким образом.
Пример выбора размера перемежителя
Для системы долгосрочной эволюции (LTE) 3GPP не является существенным определение CF-перемежителя для каждого размера блока между 40 и 5114 битами. Ограниченный или малый набор хорошо разработанных CF-перемежителей достаточен для того, чтобы охватить все размеры блока. Для неопределенных размеров блока (т.е. для которых не определены CF-перемежители) дополнение нулями (т.е. присоединение битов заполнителя) может эффективно использоваться, как описано выше.
В качестве первого примера, набор перемежителей, пригодный для охватывания размеров информационного блока для долгосрочной эволюции (LTE) 3GPP в таблице 105, определяется на основе способа полулогарифмического расслоения, описанного выше. Конкретно,
K"=2
×f,
p=4,5,…,9;
f=8,9,…,15,
p
(5)
K
K
K
K
p
f
K
K
dC
p
f
K
f
p
K
K
d
f
max
min
и ' определяется из ”. Размеры перемежителя определяются следующим образом: используя '=” и для =4,5,6,7,8,9 и =8,9,10,11,12,13,15, и используя '=”- для =4,5,6,7,8,9 и =14, охватывая  от 128 до 7680. Последние три размера (=13,14,15), соответствующие =9, могут быть удалены, так что =6144 при =128. Уравнение (3) используется вместе с =2, когда =14 (т.е. чтобы исключить размеры перемежителя, которые являются множителями 7), чтобы обрабатывать циклически замкнутые ТС. Если определены размеры перемежителя в 105, CF-перемежитель может быть разработан для каждого размера перемежителя.
K
K
K
K
K
K
f
f
b
p
f
min
max
b
b+1
При заданном любом размере  информационного блока схема 103 может определять размер ' перемежителя, подлежащий использованию для , посредством выбора наименьшего значения ' из 105, которое больше или равно . С известным  и =2, =2-1, где  представляет собой целое число, параметры и  могут быть вычислены следующим образом:
(6)
b
В частности, для параметров в (5) =3, и
p
f
K
f
K
С параметрами  и  размер ' блока может вычисляться с использованием (2) или (5), и, кроме того, когда  является кратным 7, и используется циклически замкнутое кодирование, дополнительно может использоваться размер перемежителя, вычисленный с использованием (3) или (4). Затем выполняется поиск параметров, ассоциированных с перемежителем размера ', из запоминающего средства для параметра 105 перемежителя, который обычно хранится в памяти для устройства связи.
K
В качестве второго примера, предполагаемый набор полных размеров ' перемежителя для охватывания К от 40 до 8192 битов представляет собой:
K
K
f
p
f
p
Для '∈[264, 8192], '=2×, =3,…,7; =33,34,…,64.
K
K
Для ' менее 264 используется размер шага 8, так что '=40, 48, …, 256.
Эти размеры также перечислены ниже.
40
48
56
64
72
80
88
96
104
112
120
128
136
144
152
160
168
176
184
192
200
208
216
224
232
240
248
256
264
272
280
288
296
304
312
320
328
336
344
352
360
368
376
384
392
400
408
416
424
432
440
448
456
464
472
480
488
496
504
512
528
544
560
576
592
608
624
640
656
672
688
704
720
736
752
768
784
800
816
832
848
864
880
896
912
928
944
960
976
992
1008
1024
1056
1088
1120
1152
1184
1216
1248
1280
1312
1344
1376
1408
1440
1472
1504
1536
1568
1600
1632
1664
1696
1728
1760
1792
1824
1856
1888
1920
1952
1984
2016
2048
2112
2176
2240
2304
2368
2432
2496
2560
2624
2688
2752
2816
2880
2944
3008
3072
3136
3200
3264
3328
3392
3456
3520
3584
3648
3712
3776
3840
3904
3968
4032
4096
4224
4352
4480
4608
4736
4864
4992
5120
5248
5376
5504
5632
5760
5888
6016
6144
6272
6400
6528
6656
6784
6912
7040
7168
7296
7424
7552
7680
7808
7936
8064
8192
K
Отметьте, что показанные выше размеры представляют собой только пример, определенный для максимального K' из 8192 битов и используемый в сравнительном исследовании 42 размеров информационного блока. Если используется другой максимум из 6144 битов, тогда любой ', который больше максимума, будет удаляться из списка. Также, для упрощения, размеры не учитывали различие между использованием составных кодов без циклического замыкания или циклически замкнутых составных кодов. Если турбокодер сделан циклически замкнутым, тогда могут использоваться K, которые являются кратными 7. Они или удаляются, или модифицируются, как описано ранее. Наконец, дополнительные размеры перемежителя могут добавляться к этим вышеупомянутым, чтобы уменьшить промежуток между перемежителями. Например, если используется максимальный промежуток 64, дополнительные перемежители определяются между перемежителями с промежутком 128 в таблице. Если тогда используется циклически замкнутый, и K' кратные 7 удалены, то максимальный промежуток тогда снова составляет 128.
В качестве еще другого примера выбора размера перемежителя, система может использовать CF-перемежитель только тогда, когда транспортный блок (TB) (количество информационных битов до сегментирования) превышает некоторое значение. Например, если максимальным определенным размером является 5114, когда транспортный блок превышает 5114, может использоваться CF-перемежитель, такой как ARP или QPP. В этих случаях, сегментирование может создать K' менее 5114, но CF-перемежитель используется для этого K'. K, поэтому может турбоперемежаться, используя как первый перемежитель (такой как не-CF-перемежитель 3GPP, или другой перемежитель), так и второй перемежитель (такой как бесконфликтный перемежитель), в зависимости от размера транспортного блока перед сегментированием. Первый и второй перемежитель может иметь различные наборы K'. Например, первый перемежитель может, по существу, определяться для всех K=K', тогда как второй перемежитель определяется с K', как указано выше. В некоторых случаях, единственный процессор или меньшее количество процессоров может использоваться для первого перемежителя.
Пример перемежителя ARP
C
K
C
K
C
d
A
A
K
min
Поднабор из 42 CF-перемежителей ARP, пригодных для того, чтобы охватить размеры информационных блоков для долгосрочной эволюции (LTE) 3GPP, показаны в таблице 1. Длина цикла=4 используется для <1024, =8 - для ≥1024. Большая длина  цикла приводит к лучшему минимальному расстоянию  при больших размерах блока. Также, вместо =3, =0 используется для всех размеров. Кроме того, вместо того, чтобы каждый  имел различный вектор α(·) и β(·), разрешен только небольшой набор значений α и β, чтобы уменьшить объем хранения определения перемежителя. Набор разрешенных значений α и β определен ниже.
C
Когда длина цикла =4,
α
=
β
=
C
Когда длина цикла =8,
α
=
β
=
α
β
α
β
α
β
a
b
K
a
b
C
P
a
b
C
K
C
C
C
0
Таким образом, каждая строка  может использоваться в качестве вектора α, каждая строка  может использоваться в качестве вектора β. Индекс  и , поэтому определяются для каждого , чтобы индексировать строки  и , где 1<=<=2, 1<=<=2. Способ индексирования существенно уменьшает запоминающее устройство перемежителя ARP, так как только  (8 битов), индекс  (1 бит) и  (3-4 бита) необходимо хранить для перемежителя. Длина  цикла может определяться на основе того, меньше ли  1024 битов. Кроме того, величина запоминающего устройства параметров для использования =8 в сопоставлении с =4 представляет собой только разницу в размере матрицы  и , что является тривиальным, поэтому допускает свободу использования больших , если необходимо.
K
C
P
K
C
P
0
0
Запоминающее средство для параметра 105 перемежителя может хранить параметры перемежителя ARP, используя значения ', , , α(·) и β(·), которые берутся, по меньшей мере, из одной строки таблицы 1. Перемежитель 201 может использовать перемежитель ARP со значениями ', , , α(·) и β(·), которые берутся, по меньшей мере, из одной строки следующей таблицы:
Таблица 1.Параметры набора перемежителей ARP, определенных для LTE. Постоянное смещение <i>A</i>=0 используется для всех размеров. Перечислены возможные параллельности М, использующие естественно параллельные окна, меньшие или равные 32
<b>K_info</b>
<b>K</b>
<b>C</b>
<b>P</b><sub>0</sub>
<b>Индекс а</b>
<b>Индекс b</b>
<b>Доступная параллельность</b>
40
40
4
41
1
6
1,2,5,10
52
56
4
13
1
1
1,2,7,14
67
72
4
13
1
4
1,2,3,6,9,18
87
88
4
75
2
3
1,2,11,22
99
104
4
23
1
1
1,2,3,26
113
120
4
73
1
8
1,2,3,5,6,10,15,30
129
136
4
11
1
6
1,2,17
146
152
4
129
1
5
1,2,19
167
168
4
25
1
4
1,2,3,6,7,14,21
190
192
4
43
1
1
1,2,3,4,6,8,12,16,24
216
216
4
133
1
1
1,2,3,6,9,18,27
246
248
4
57
2
6
1,2,31
280
280
4
33
2
1
1,2,5,7,10,14
319
320
4
207
1
4
1,2,4,5,8,10,16,20
363
368
4
877
2
3
1,2,4,23
384
384
4
91
1
1
1,2,3,4,6,8,12,16,24,32
414
416
4
77
1
1
1,2,4,8,13,26
471
472
4
61
1
4
1,2
536
544
4
237
1
1
1,2,4,8,17
611
624
4
49
1
7
1,2,3,4,6,12,13,26
695
704
4
43
1
4
1,2,4,8,11,16,22
792
800
4
151
1
1
1,2,4,5,8,10,20,25
902
912
4
49
1
1
1,2,3,4,6,12,19
1027
1056
8
217
2
1
1,2,3,4,6,11,12,22
1169
1184
8
49
1
11
1,2,4
1331
1344
8
253
2
2
1,2,3,4,6,7,8,12,14,21,24,28
1536
1536
8
187
2
8
1,2,3,4,6,8,12,16,24,32
1725
1728
8
65
1
3
1,2,3,4,6,8,9,12,18,24,27
1965
1984
8
121
1
14
1,2,4,8,31
2237
2240
8
137
2
6
1,2,4,5,7,8,10,14,20,28
2304
2304
8
193
1
4
1,2,3,4,6,8,9,12,16,18,24,32
2547
2560
8
157
1
3
1,2,4,5,8,10,16,20,32
2900
2944
8
121
1
7
1,2,4,8,16,23
3302
3328
8
137
2
1
1,2,4,8,13,16,26,32
3760
3776
8
119
1
3
1,2,4,8
4096
4096
8
169
2
11
1,2,4,8,16,32
4281
4352
8
179
1
3
1,2,4,8,16,17,32
4874
4992
8
211
1
3
1,2,3,4,6,8,12,13,16,24,26
5550
5632
8
237
1
7
1,2,4,8,11,16,22,32
6144
6144
8
253
2
13
1,2,3,4,6,8,12,16,24,32
7195
7296
8
181
1
7
1,2,3,4,6,8,12,16,19,24
8192
8192
8
203
1
7
1,2,4,8,16,32
Свойства перемежителя ARP
C
Существует несколько путей модифицирования таблицы перемежителя. Например, запоминающее устройство может быть уменьшено посредством использования набора параметров ARP, которые применяются к более чем одному размеру перемежителя. Например, 1024-битовый, 2048-битовый, 4096-битовый перемежители все могут использовать одни и те же параметры ARP. В другом варианте, некоторые строки таблицы могут быть переработаны на основе различных значений , если необходимо. При другом улучшении, некоторые элементы параметров (например, α(0) и β(0)) могут быть фиксированными (например, всегда нулевыми).
Ниже представлены некоторые дополнительные замечания по процедуре выбора перемежителя, используемые для получения таблицы 1.
A
1. Постоянное значение смещения =3 или A=0 выбирается для уменьшения запоминающего устройства.
C
K
C
K
2. Основываясь на исследовании рабочих характеристик и запоминающем устройстве, длина цикла =4 используется для '<1024, =8 - для '≥1024.
3. Для каждого размера блока выполнялись имитации, чтобы гарантировать, что рабочие характеристики перемежителя ARP (с циклически замкнутым кодированием) близки или лучше, чем рабочие характеристики с перемежителем, определенным в спецификации для турбокода 3GPP.
4. Таблица 1, основанная на (5), была определена для того, чтобы охватывать конкретный набор размеров перемежителя (например, 40-8192). Если является предпочтительным, могут быть удалены или добавлены другие размеры перемежителя.
5. Все перемежители, определенные в 105, которые не являются кратными 7, могут использоваться или для турбокодов без циклического замыкания, или для циклически замкнутых турбокодов, в зависимости от допустимого ухудшения рабочих характеристик. Те, которые являются кратными 7, также могут использоваться без циклического замыкания.
Пример перемежителя QPP
Поднабор из 42 CF-перемежителей QPP, пригодных для того, чтобы охватывать размеры информационного блока для долгосрочной эволюции (LTE) 3GPP, показан в таблице 2. Эти перемежители имеют квадратный обратный многочлен, так что деперемежитель также представляет собой QPP.
K
f1
f2
K
f1
f2
Запоминающее средство для параметра 105 перемежителя может хранить параметры перемежителя QPP, используя значения ', , , которые берутся из, по меньшей мере, одной строки таблицы 2. Перемежитель 201 может использовать перемежитель QPP со значениями ', , , которые берутся из, по меньшей мере, одной строки следующей таблицы:
Таблица 2Параметры набора перемежителей QPP, определенных для LTE. Перечислены возможные параллельности меньше или равные 32
<b>K_info</b>
<b>K</b>
<b>f1</b>
<b>f2</b>
<b>Доступная параллельность</b>
40
40
37
20
1,2,4,5,8,10,20
52
56
19
42
1,2,4,7,8,14,28
67
72
19
60
1,2,3,4,6,8,9,12,18,24
87
88
5
22
1,2,4,8,11,22
99
104
45
26
1,2,4,8,13,26
113
120
103
90
1,2,3,4,5,6,8,10,12,15,20,24,30
129
136
19
102
1,2,4,8,17
146
152
135
38
1,2,4,8,19
167
168
101
84
1,2,3,4,6,7,8,12,14,21,24,28
190
192
85
24
1,2,3,4,6,8,12,16,24,32
216
216
13
36
1,2,3,4,6,8,9,12,18,24,27
246
248
33
62
1,2,4,8,31
280
280
103
210
1,2,4,5,7,8,10,14,20,28
319
320
21
120
1,2,4,5,8,10,16,20,32
363
368
25
138
1,2,4,8,16,23
384
384
25
240
1,2,3,4,6,8,12,16,24,32
414
416
77
52
1,2,4,8,13,16,26,32
471
472
175
118
1,2,4,8
536
544
35
68
1,2,4,8,16,17,32
611
624
41
234
1,2,3,4,6,8,12,13,16,24,26
695
704
155
44
1,2,4,8,11,16,22,32
792
800
207
80
1,2,4,5,8,10,16,20,25,32
902
912
85
114
1,2,3,4,6,8,12,16,19,24
1027
1056
229
132
1,2,3,4,6,8,11,12,16,22,24,32
1169
1184
217
148
1,2,4,8,16,32
1331
1344
211
252
1,2,3,4,6,7,8,12,14,16,21,24,28,32
1536
1536
71
48
1,2,3,4,6,8,12,16,24,32
1725
1728
127
96
1,2,3,4,6,8,9,12,16,18,24,27,32
1965
1984
185
124
1,2,4,8,16,31,32
2237
2240
209
420
1,2,4,5,7,8,10,14,16,20,28,32
2304
2304
253
216
1,2,3,4,6,8,9,12,16,18,24,32
2547
2560
39
240
1,2,4,5,8,10,16,20,32
2900
2944
231
184
1,2,4,8,16,23,32
3302
3328
51
104
1,2,4,8,13,16,26,32
3760
3776
179
236
1,2,4,8,16,32
4096
4096
95
192
1,2,4,8,16,32
4281
4352
477
408
1,2,4,8,16,17,32
4874
4992
233
312
1,2,3,4,6,8,12,13,16,24,26,32
5550
5632
45
176
1,2,4,8,11,16,22,32
6144
6144
263
480
1,2,3,4,6,8,12,16,24,32
7195
7296
137
456
1,2,3,4,6,8,12,16,19,24,32
8192
8192
417
448
1,2,4,8,16,32
K
K
K
K
Фиг.3 представляет собой блок-схему приемника 300. На входе схема 302 обработки заполнителя принимает вектор сигнала, который, возможно, был передан по каналу, например, по радиоканалу. Схема 306 затем определяет размер ' перемежителя, что может быть сделано аналогично тому, что описано выше, например, посредством выполнения поиска в таблице в запоминающем устройстве 308, или при помощи вычислений, таких как (7), (8) и (2). Поэтому при заданном размере  информационного блока декодер 304 использует этот же размер ' перемежителя, что и тот, который использовался кодером 101. Схема 302 обработки заполнителя используется для соответствующей обработки вектора принятого сигнала и положений битов заполнителя (например, если положения битов заполнителя известны, тогда соответствующие величины LLR могут быть установлены на очень высокие величины во время декодирования). Затем турбодекодер 304 выполняет декодирование и получает оценку  входного блока длины '. Наконец, схема 310 извлечения информационного блока извлекает оцененный информационный блок из . Хотя схема 302 обработки заполнителя показана вне турбодекодера для простоты объяснения, эти две схемы могут быть объединены при реализации.
K
K
K
K
a
f
p
p
p
f
f
f
a
f
f
f
p
p
p
a
p
p
p
K
p
min
max
min
max
min
max
min
max
max
min
min
filler
Фиг.4 представляет собой блок-схему турбодекодера по фиг.3. Как очевидно, перемежитель 402 и деперемежитель 401 находятся между схемой 403 декодирования и схемой 404 декодирования. Итеративное декодирование происходит так, как известно в технике, однако, в отличие от декодеров известного уровня техники, размер ' перемежителя связан с ”, где ” из набора размеров; причем набор размеров содержит ”=×, ≤≤; ≤≤, причем  представляет собой целое число,  представляет собой постоянное целое число между  и , и  принимает целочисленные значения между  и , >1, >, >1. Параметр  может быть необходим или может быть необязательным для турбодекодера 304, таким образом обозначен пунктирной линией на фиг.4.
K
K
K
K
K
K
K
K
K
m
K
m
m
m
m
Как описано выше, в одном варианте осуществления '=”. В еще другом варианте осуществления '=”, когда ” не является кратным (2-1), в противном случае использование '=”+δ(”), когда ” является кратным (2-1), причем  представляет собой емкость памяти составного сверточного кодера, и δ(”) представляет собой небольшое положительное или отрицательное целое число, не равное кратному (2-1). В одном варианте осуществления =3.
π
i
iP
A
d
i
K
i
K
π
i
i
K
P
K
А
С
K
d
i
d
i
β
i
C
P
α
i
C
С
i
K
K
C
P
0
0
0
0
Перемежитель 402 может использовать перестановку ()=(++())mod', где 0≤≤'-1 представляет собой последовательный индекс положений символа после перемежения, () представляет собой индекс символа перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в символах,  представляет собой число, которое является относительно простым для ',  представляет собой постоянную,  представляет собой небольшое число, которое делит ', и () представляет собой вектор возмущения вида ()=(mod)+×(mod), где α(·) и β(·) представляют собой векторы, каждый длиной , периодически применяемые для 0≤≤'-1. Значения ', , , α(·) и β(·), предпочтительно, берутся из строки таблицы 1. Деперемежитель 401 выполняет функцию, обратную функции перемежителя 402.
π
i
f
i
f
i
K
i
K
i
i
K
f
f
K
f1
f2
1
2
1
2
2
Перемежитель 402 может использовать перестановку ()=(×+×)mod', где 0≤≤'-1 представляет собой последовательный индекс положений символа после перемежения, π() представляет собой индекс символа перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в символах, и  и  представляют собой коэффициенты, определяющие перемежитель. Значения ', , , предпочтительно, берутся из строки таблицы 2. Деперемежитель 401 выполняет функцию, обратную функции перемежителя 402.
K
K
K
K
a
f, p
p
p
f
f
f
a
f
f
f
p
p
p
a
p
p
p
K
K
K
K
K
K
K
K
K
m
K
m
p
m
m
m
min
max
min
max
min
max
min
max
max
min
min
Фиг.5 представляет собой блок-схему последовательности операций, изображающую работу передатчика 100. Логическая последовательность операций начинается на этапе 501, где схема 103 определяет размер ' перемежителя, который связан с ”, где ” из набора размеров; причем набор размеров содержит ”=×≤≤; ≤≤, причем  представляет собой целое число,  представляет собой постоянное целое число между  и , и  принимает целочисленные значения между  и , >1, >, >1. Как описано выше, в одном варианте осуществления '=”. В еще другом варианте осуществления '=”, когда ” не является кратным (2-1), в противном случае использование '=”+δ(”), когда ” является кратным (2-1), причем  представляет собой емкость памяти составного сверточного кодера, и δ(”) представляет собой небольшое положительное или отрицательное целое число, не равное кратному (2-1). В одном варианте осуществления =3.
K
K
K
K
K
u
u
На этапе 503 схема 109 вставки заполнителя принимает информационный блок размера  и заполняет информационный блок размера  во входной блок  размера ' и выводит входной блок . Перемежитель 201 затем перемежает входной блок размера ' (этап 507) (предпочтительно используя бесконфликтный перемежитель) и посылает перемеженный блок размера ' на схему 203 кодирования (этап 509). Наконец, на этапе 511 кодируются исходный входной блок и перемеженный входной блок.
π
i
iP
A
d
i
K
i
K
i
i
K
P
K
А
С
K
d
i
d
i
β
i
C
P
α
i
C
C
i
K
K
C
P
π
i
f
i
f
i
K
i
K
i
i
K
f
f
K
f1
f2
0
0
0
0
1
2
1
2
2
Как описано выше, этап перемежения входного блока может содержать этап использования перестановки ()=(++())mod', где 0≤≤'-1 представляет собой последовательный индекс положений бита после перемежения, π() представляет собой индекс бита перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в битах,  представляет собой число, которое является относительно простым для ',  представляет собой постоянную,  представляет собой небольшое число, которое делит ', и () представляет собой вектор возмущения вида ()=(mod)+×(mod), где α(·) и β(·) представляют собой векторы, каждый длиной , периодически применяемые для 0≤≤'-1. Значения ', , , α(·) и β(·) берутся, предпочтительно, из таблицы 1. Этап перемежения входного блока также может содержать этап использования перестановки ()=(×+×)mod', где 0≤≤'-1 представляет собой последовательный индекс положений символа после перемежения, π() представляет собой индекс символа перед перемежением, соответствующий положению , ' представляет собой размер перемежителя в символах, и  и  представляют собой коэффициенты, определяющие перемежитель. Значения ', ,  берутся, предпочтительно, из строки таблицы 2.
K
K
K
K
Фиг.6 представляет собой блок-схему последовательности операций, изображающую работу приемника по фиг.3. Логическая последовательность операций начинается на этапе 601, где схема 306 определяет размер ' перемежителя. На этапе 603 схема 302 добавляет информацию битов заполнителя в вектор принятого сигнала, например, если известны биты заполнителя и положения битов заполнителя, схема 302 может устанавливать на высокие величины логарифмического отношения правдоподобия (LLR) этих положений во входе турбодекодера. На этапе 607 турбодекодер декодирует входной блок декодера, используя перемежитель и деперемежитель размера ', и выводит оцененный  входного блока длины '. На этапе 609 схема 310 извлечения информационного блока удаляет биты заполнителя для получения оценки информационного блока длины . Наконец, на этапе 611 выводится оцененный информационный блок.
Хотя изобретение было конкретно показано и описано со ссылкой на конкретный вариант осуществления, для специалиста в данной области техники понятно, что в нем могут быть выполнены различные изменения в форме и деталях без отступления от сущности и объема изобретения. В одном примере, таблица перемежителя может быть дополнительно улучшена для обработки специальных случаев, включающих в себя: (а) Использование дополнительного набора размеров перемежителя, определенных для того, чтобы охватывать любые специальные размеры блока, которые должны обрабатываться, например, без битов заполнителя или с меньшим количеством битов заполнителя. (b) Размеры перемежителя могут незначительно подстраиваться посредством добавления или вычитания малого значения из размеров полулогарифмического расслоения. В другом примере, хотя изобретение было описано выше, предполагая турбокодер с бинарным входом, этот же принцип может быть применен, когда турбокодер принимает символы в качестве входа. Например, дуобинарный турбокод принимает символ из двух двоичных разрядов за один раз, и турбоперемежитель выполняет перестановку символов (дополнительно может выполняться скремблирование, такое как чередование битов в символе). В таком случае, размер входного блока измеряется в символах, и размер перемежителя равен количеству символов во входном блоке. В другом примере, хотя вышеупомянутое описание предполагает, что размеры перемежителя и параметры перемежителя хранятся в таблице поиска, возможно, что они могут определяться при помощи других средств, таких как алгебраическое вычисление. В еще другом примере, хотя вышеупомянутое описание предполагает турбокод, способ также применим к другим схемам прямой коррекции ошибок (FEC), включающим в себя, например, коды с низкой плотностью проверок на четность (LDPC), коды Рида-Соломона (RS) и т.д. Предполагается, что такие изменения подпадают под объем нижеследующей формулы изобретения.