[go: up one dir, main page]

RU98100587A - OPTIMAL DECODER PROGRAMMABLE DETAILS FOR GRIDED CODES WITH FINITE SEQUENCE BITS - Google Patents

OPTIMAL DECODER PROGRAMMABLE DETAILS FOR GRIDED CODES WITH FINITE SEQUENCE BITS

Info

Publication number
RU98100587A
RU98100587A RU98100587/09A RU98100587A RU98100587A RU 98100587 A RU98100587 A RU 98100587A RU 98100587/09 A RU98100587/09 A RU 98100587/09A RU 98100587 A RU98100587 A RU 98100587A RU 98100587 A RU98100587 A RU 98100587A
Authority
RU
Russia
Prior art keywords
probability
elements
encoder
vectors
state
Prior art date
Application number
RU98100587/09A
Other languages
Russian (ru)
Other versions
RU2179367C2 (en
Inventor
Майкл Хладик Стефен
Бейли Андерсон Джон
Original Assignee
Дженерал Электрик Компани
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US08/636,742 external-priority patent/US5721746A/en
Application filed by Дженерал Электрик Компани filed Critical Дженерал Электрик Компани
Publication of RU98100587A publication Critical patent/RU98100587A/en
Application granted granted Critical
Publication of RU2179367C2 publication Critical patent/RU2179367C2/en

Links

Claims (25)

1. Декодер для решетчатого кода с конечной последовательностью битов, генерируемого кодером, отличающийся тем, что упомянутый декодер обеспечивает декодирование путем определения совместной вероятности того, что состояние St кодера в момент t есть m, и что принята последовательность из L выходных сигналов каналов, имеющих значения YLl = {yl,...,yL}, что соответствует λt(m) = P{St= m; Y L l }, причем упомянутый решетчатый код имеет М состояний кодера, декодер определяет L матриц вероятности Гt, по одной для каждого из L уровней решетчатого кода, элементы упомянутых матриц вероятности определяются соотношением
Гt(i, j) = Р{состояние j в момент времени t-l; yt/состояние i в момент времени t-l};
путем определения векторов-строк αt, имеющих М элементов совместной вероятности, определяемых соотношением
Figure 00000001

и путем определения векторов-столбцов βt, имеющих М элементов условной вероятности, определяемых соотношением
Figure 00000002

для j = 0,...,(М-1), причем упомянутый декодер содержит вычислитель Гt для приема упомянутых выходных сигналов канала, вероятности перехода канала R(Yt, X), вероятности pt(m/m'), что кодер осуществляет переход из состояния m' в состояние m в момент времени t, и вероятность qtX/m',m) того, что выходной символ кодера есть Х при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера есть m, и для определения из указанных данных скалярных элементов упомянутых матриц Гt, вычислитель произведения матриц Гt для приема упомянутых скалярных элементов с вычислителя Гt и вычисления из них матричного произведения Г1Г2. ..ГL, вычислитель нормированного собственного вектора для приема матричного произведения Г1Г2...ГL и вычисления нормированного собственного вектора, соответствующего наибольшему собственному значению P{ YLl} упомянутого матричного произведения, вычислитель произведения матриц αt для приема нормированного собственного вектора α0 и формирования последующего значения αt путем прямой рекурсии в соответствии с выражением
αt= αt-1Гt, y = l,...,L;
память для хранения матриц вероятности Гt и векторов-строк αt,
вычислитель произведения матриц βt для формирования векторов-столбцов путем инициализации βL= (l, l,l,...,l)T и для формирования предыдущего βt путем обратной рекурсии в соответствии с соотношением
βt= Гt+1βt+1, t = L-l,...,l;
вычислитель поэлементного произведения для формирования векторов совместной вероятности λt, элементы которой являются упомянутыми совместными вероятностями λt(i,j), путем умножения элементов векторов-строк на элементы векторов-столбцов согласно соотношению
λt(i) = αt(i)βt(i), для всех i, t = l,...,L;
вычислитель вероятности значения декодированного бита для определения из λt вероятности того, что заданный бит данных, введенный в кодер в момент времени t, равен нулю, причем бит данных является m-ым битом из k битов данных, и для формирования программируемого выходного результата в качестве функции указанной вероятности.
1. A decoder for a trellis code with a finite sequence of bits generated by the encoder, characterized in that said decoder provides decoding by determining the joint probability that the encoder state S t at time t is m, and that the received sequence of L output signals of channels having values Y L l = {y l , ..., y L }, which corresponds to λ t (m) = P {S t = m; Y L l }, moreover, said lattice code has M states of the coder, the decoder determines L probability matrices Γ t , one for each of the L levels of the lattice code, the elements of the said probability matrices are determined by the relation
Г t (i, j) = Р {state j at the moment of time tl; y t / state i at time tl};
by determining the row vectors α t having M elements of joint probability, determined by the ratio
Figure 00000001

and by determining the column vectors β t having M conditional probability elements, defined by the ratio
Figure 00000002

for j = 0, ..., (M-1), moreover, said decoder contains calculator G t for receiving said channel output signals, channel transition probability R (Y t , X), probability p t (m / m '), that the encoder transitions from the state m 'to the state m at the moment of time t, and the probability q t X / m', m) that the output symbol of the encoder is X provided that the previous state of the encoder is m 'and the current state of the encoder there is m, and for determining from the above given scalar elements of the mentioned matrices G t , the calculator is the product of the matrices G t for receiving the mentioned scalar elements ments with calculator and calculating T t are the matrix product r 1 r 2. .. G L , calculator of the normalized eigenvector for receiving the matrix product G 1 G 2 ... G L and calculating the normalized eigenvector corresponding to the largest eigenvalue P {Y L l } of the matrix product, calculator of the product of matrices α t for receiving the normalized eigenvector α 0 and the formation of the subsequent value α t by direct recursion in accordance with
α t = α t-1 G t , y = l, ..., L;
memory for storing matrices of probability Г t and row vectors α t ,
the calculator of the product of matrices β t for the formation of column vectors by initializing β L = (l, l, l, ..., l) T and for forming the previous β t by reverse recursion in accordance with the relation
β t = Г t + 1 β t + 1 , t = Ll, ..., l;
an elementwise product calculator for generating joint probability vectors λ t , whose elements are the said joint probabilities λ t (i, j), by multiplying the elements of the row vectors by the elements of the column vectors according to the relation
λ t (i) = α t (i) β t (i), for all i, t = l, ..., L;
the probability calculator of the decoded bit value to determine from λ t the probability that the specified data bit entered into the encoder at time t is zero, and the data bit is the m-th bit of the k data bits, and to generate a programmable output as functions of the specified probability.
2. Декодер по п. 1, отличающийся тем, что дополнительно содержит устройство пороговой обработки для приема вероятности того, что бит данных, введенный в кодер в момент времени t, равен нулю и для реализации решающего правила для формирования декодированных выходных битов. 2. The decoder according to claim 1, characterized in that it further comprises a threshold processing device for receiving the probability that the data bit entered into the encoder at time t is zero and for implementing a decision rule for generating decoded output bits. 3. Декодер по п. 1, отличающийся тем, что упомянутый решеточный код с конечной последовательностью битов представляет собой сверточный код. 3. The decoder according to claim 1, characterized in that said grating code with a finite sequence of bits is a convolutional code. 4. Декодер по п.1, отличающийся тем, что содержит декодер с ограниченным кодовым расстоянием. 4. The decoder according to claim 1, characterized in that it contains a decoder with a limited code distance. 5. Декодер для решетчатого кода с конечной последовательностью битов, генерируемого кодером, отличающийся тем, что упомянутый декодер обеспечивает декодирование путем определения совместной вероятности того, что состояние St кодера в момент t есть m, и что принята последовательность из L выходных сигналов каналов, имеющих значения YLl = {yl,...,yL}, что соответствует λt(m) = P{St= m; Y L l }, причем упомянутый решетчатый код имеет М состояний кодера, декодер определяет L матриц условной вероятности Гt, по одной для каждого из L уровней решетчатого кода, элементы упомянутых матриц вероятности определяются соотношением
Гt(i, j) = Р{ состояние j в момент времени t; yt/состояние i в момент времени t-l};
путем определения векторов-строк αt, имеющих М элементов совместной вероятности, определяемых соотношением
Figure 00000003

и путем определения векторов-столбцов βt, имеющих М элементов условной вероятности, определяемых соотношением
Figure 00000004

для j = 0,...,(М-1), причем упомянутый декодер содержит вычислитель Гt для приема упомянутых выходных сигналов канала, вероятности перехода канала R(Yt, X), вероятности pt(m/m'), что кодер осуществляет переход из состояния m' в состояние m в момент времени t, и вероятность qtX/m',m) того, что выходной символ кодера есть Х при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера есть m, и для определения из указанных данных скалярных элементов упомянутых матриц Гt, вычислитель произведения матриц αt для приема упомянутых скалярных элементов Гt с вычислителя Гt и формирования векторов-строк αt, вычислитель произведения матриц βt для формирования векторов-столбцов βt, вычислитель поэлементных произведений для формирования векторов совместной вероятности λt, элементы которой являются упомянутыми совместными вероятностями λt(i,j), причем упомянутые вычислитель произведения матриц αt, вычислитель произведения матриц βt и вычислитель поэлементных произведений формируют указанные векторы αttt путем
(i. a) вычисления, начиная с начального α0, равного (1/М, ..., 1/М), рекурсии вперед L раз в виде αt= αt-1Гt, t = l,...,L и нормирования результатов так, чтобы элементы каждого нового αt суммировались до единицы, с сохранением всех L векторов αt,
(i. b) вычисления, принимая α0 равным αL из этапа (i.a) и начиная с момента t = l, αt= αt-lГt, t = 1,2,...,Lw min, где Lw min - соответствующее минимальное число каскадов решетчатого кода, и нормирования результатов так, чтобы элементы каждого нового αt суммировались до единицы, с сохранением только самого последнего множества из L векторов α, найденных путем рекурсивного вычисления согласно этапам (i.a) и (i.b), и αLw min, найденного на этапе (i.a),
(ii.c) сравнения αLw min, полученного на этапе (i.b), с αLw min, полученным на этапе (i.a), и перехода, при нахождении в пределах поля допуска, к этапу (ii), или продолжения обработки, в противном случае, на этапе (i.d),
(i. d) вычисления, при t = t + 1, αt= αt-1Гt, нормирования результатов рекурсивного вычисления так, чтобы элементы каждого нового αt суммировались до единицы, с сохранением только самого последнего множества из L вычисленных векторов αt и αt, найденных ранее на этапе (i.a),
(i.e) сравнения новых значений αt с самыми последними ранее вычисленными на этапах (i. a), (i.b), (i.d) значениями αt и перехода, при нахождении в пределах поля допуска, к этапу (ii), или продолжения обработки на этапе (i. d), если два самых последних вектора не совпадают в пределах поля допуска и если число рекурсий не превысило определенный максимум, и перехода к этапу (ii) в противном случае,
(ii) инициализации βL= (l, l,l,...,l)T и формирования предыдущего βt путем обратной рекурсии в соответствии с соотношением
βt= Гt+1βt+1, t = L-l,...,l;
и нормирования результатов рекурсии так, чтобы элементы каждого βt суммировались до единицы, с сохранением всех L векторов βt,
(iii) формирования векторов совместной вероятности λt, элементы которой являются упомянутыми совместными вероятностями λt(i,j), путем умножения элементов векторов-строк на элементы векторов-столбцов согласно соотношению
λt(i) = αt(i)βt(i), для всех i, t = l,...,L;
память для хранения упомянутых матриц вероятности и векторов-строк и вычислитель вероятности декодированного значения бита для определения из λt вероятности того, что заданный бит данных, введенный в кодер в момент времени t, равен нулю, причем бит данных является m-ым битом из k битов данных, и для формирования программируемого выходного результата в качестве функции указанной вероятности.
5. A decoder for a trellis code with a finite sequence of bits generated by the encoder, characterized in that said decoder provides decoding by determining the joint probability that the encoder state S t at time t is m, and that the received sequence of L output signals of channels having values Y L l = {y l , ..., y L }, which corresponds to λ t (m) = P {S t = m; Y L l }, moreover, the said lattice code has M states of the encoder, the decoder determines L conditional probability matrices G t , one for each of the L levels of the lattice code, the elements of the said probability matrices are determined by the relation
Г t (i, j) = Р {state j at the moment of time t; y t / state i at time tl};
by determining the row vectors α t having M elements of joint probability, determined by the ratio
Figure 00000003

and by determining the column vectors β t having M conditional probability elements, defined by the ratio
Figure 00000004

for j = 0, ..., (M-1), moreover, said decoder contains calculator G t for receiving said channel output signals, channel transition probability R (Y t , X), probability p t (m / m '), that the encoder transitions from the state m 'to the state m at the moment of time t, and the probability q t X / m', m) that the output symbol of the encoder is X provided that the previous state of the encoder is m 'and the current state of the encoder there is m, and for determining from the above given scalar elements of the said matrices G t , the calculator is the product of the matrices α t for receiving said scalar elements cops Г t с calculator Г t and formation of row vectors α t , calculator of matrix products β t for forming column vectors β t , calculator of elementwise products for formation of joint probability vectors λ t , whose elements are mentioned joint probabilities λ t (i, j), moreover, the said transmitter works of matrices α t , the transmitter works of matrices β t and the transmitter element-wise products form the specified vectors α t , β t , λ t by
(i. a) calculations starting from the initial α 0 equal to (1 / M, ..., 1 / M), forward recursion L times in the form α t = α t-1 Г t , t = l, .. ., L and the valuation of the results so that the elements of each new α t sum up to one, with the preservation of all L vectors α t ,
(i. b) calculations, taking α 0 equal to α L from stage (ia) and starting from the moment t = l, α t = α tl Г t , t = 1,2, ..., L w min , where L w min is the corresponding minimum number of cascades of the trellis code, and the valuation of the results so that the elements of each new α t sum up to one, while retaining only the most recent set of L vectors α found by recursive calculation according to steps (ia) and (ib), and α Lw min found in step (ia),
(ii.c) comparing α Lw min obtained in step (ib) with α Lw min obtained in step (ia) and the transition, if within the tolerance field, to step (ii), or continuing processing, in otherwise, at the (id) stage,
(i. d) calculations, with t = t + 1, α t = α t-1 Г t , normalization of the results of recursive calculations so that the elements of each new α t sum up to one, with only the latest set of L calculated vectors α t and α t , found earlier in step (ia),
(ie) comparing new values of α t with the most recently calculated at stages (i. a), (ib), (id) values of α t and the transition, while within the tolerance field, to stage (ii), or continuing processing at stage (i. d), if the two most recent vectors do not coincide within the tolerance range and if the number of recursions did not exceed a certain maximum, and go to stage (ii) otherwise,
(ii) initialization β L = (l, l, l, ..., l) T and formation of the previous β t by reverse recursion in accordance with the relation
β t = Г t + 1 β t + 1 , t = Ll, ..., l;
and normalizing the results of recursion so that the elements of each β t sum up to unity, with all the L vectors β t being saved,
(iii) the formation of joint probability vectors λ t , whose elements are the above mentioned joint probabilities λ t (i, j), by multiplying the elements of the row vectors by the elements of the column vectors according to the relation
λ t (i) = α t (i) β t (i), for all i, t = l, ..., L;
memory for storing the said probability matrices and row vectors and the probability calculator of the decoded bit value to determine from λ t the probability that the specified data bit entered into the encoder at time t is zero, and the data bit is the m-th bit of k data bits, and to generate a programmable output as a function of a specified probability.
6. Декодер по п. 5, отличающийся тем, что дополнительно содержит устройство пороговой обработки для приема значения вероятности того, что бит данных, введенный в кодер в момент времени t, равен нулю и для реализации решающего правила для формирования декодированных выходных битов. 6. The decoder according to claim 5, characterized in that it further comprises a threshold processing device for receiving a probability value that the data bit entered into the encoder at time t is zero and for implementing a decision rule for generating decoded output bits. 7. Декодер по п. 5, отличающийся тем, что упомянутый решеточный код с конечной последовательностью битов представляет собой сверточный код. 7. The decoder according to claim 5, characterized in that said grating code with a finite sequence of bits is a convolutional code. 8. Декодер по п.5, отличающийся тем, что содержит декодер с ограниченным кодовым расстоянием. 8. The decoder according to claim 5, characterized in that it contains a decoder with a limited code distance. 9. Декодер по п.5, отличающийся тем, что кодер обеспечивает кодирование блока битов данных, причем биты данных сгруппированы в k-битовые символы для кодирования, причем предварительно определенное максимальное число рекурсий содержит двукратное число k-битовых входных символов в блоке битов данных. 9. The decoder according to claim 5, wherein the encoder encodes a block of data bits, the data bits are grouped into k-bit symbols for encoding, and the predetermined maximum number of recursions contains twice the number of k-bit input symbols in the data bit block. 10. Декодер для решетчатого кода с конечной последовательностью битов, генерируемого кодером, отличающийся тем, что упомянутый декодер обеспечивает декодирование путем определения совместной вероятности того, что состояние St кодера в момент t есть m, и что принята последовательность из L выходных сигналов каналов, имеющих значения YLl = {yl,...,yL}, что соответствует λt(m) = P{St= m; Y L l }, причем упомянутый решетчатый код имеет М состояний кодера, декодер определяет L матриц условной вероятности Гt, по одной для каждого из L уровней решетчатого кода, элементы упомянутых матриц вероятности определяются соотношением
Гt(i, j) = Р{ состояние j в момент времени t; yt/состояние i в момент времени t-l};
путем определения векторов-строк αt, имеющих М элементов совместной вероятности, определяемых соотношением
Figure 00000005

и путем определения векторов-столбцов βt, имеющих М элементов условной вероятности, определяемых соотношением
Figure 00000006

для j = 0,...,(М-1), причем упомянутый декодер содержит вычислитель Гt для приема упомянутых выходных сигналов канала, вероятности перехода канала R(Yt, X), вероятности pt(m/m'), что кодер осуществляет переход из состояния m' в состояние m в момент времени t, и вероятность qt(X/m',m) того, что выходной символ кодера есть Х при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера есть m, и для определения из указанных данных скалярных элементов упомянутых матриц вероятностей Гt, вычислитель произведения матриц αt для приема упомянутых скалярных элементов Гt с вычислителя Гt и формирования векторов-строк αt, вычислитель произведения матриц βt для формирования векторов-столбцов βt, вычислитель поэлементных
произведений для формирования векторов совместной вероятности λt, причем упомянутые вычислитель произведения матриц αt, вычислитель произведения матриц βt и вычислитель поэлементных произведений формируют указанные векторы αttt путем
(i. a) вычисления, начиная с начального α0, равного (1/М, ..., 1/М), рекурсии вперед L раз в виде αt= αt-1Гt, y = l,...,L и нормирования результатов так, чтобы элементы каждого αt суммировались до единицы, с сохранением всех L векторов αt,
(i. b) вычисления, принимая α0 равным αL из этапа (i.a) и начиная с момента t = l, αt= αt-lГt, t = 1,2,...,Lw, где глубина цикла Lw представляет собой предварительно определенное число каскадов решетчатого кода, и нормирования результатов так, чтобы элементы каждого αt суммировались до единицы, заменяя αt, вычисленные на этапе (i.a), на αt, вычисленные на этапе (i.b), для t = 1, 2,...Lw,
(ii. a) инициализации βL= (l, l,l,...,l)T и для формирования предыдущего βt путем обратной рекурсии в соответствии с соотношением
βt= Гt+1βt+1, t = L-l,...,l;
и нормирования результатов рекурсии так, чтобы элементы каждого βt суммировались до единицы, с сохранением всех L векторов βt,
(ii.b) вычисления, при βL+1 равном βl, согласно этапу (ii.a), и при ГL+1 равном Г1, начиная с t = L,
βt= Гt+1βt+1, для t = L,L-1,...,L-(Lw+l);
где глубина цикла Lw представляет собой предварительно определенное число каскадов решетчатого кода, и нормирования результатов рекурсии так, чтобы элементы каждого βt суммировались до единицы, с заменой векторов βt, вычисленных на этапе (ii.а), значениями βt, вычисленными на этапе (ii.b), для t=L,L-l,....L-(Lw+l);
(iii) формирования векторов совместной вероятности λt, элементы которой являются упомянутыми совместными вероятностями λt(i,j), путем умножения элементов векторов-строк на элементы векторов-столбцов согласно соотношению
λt(i) = αt(i)βt(i), для всеx i, t = l,...,L;
память для хранения упомянутых матриц вероятности и векторов-строк и вычислитель вероятности значения декодированного бита для определения из λt вероятности того, что заданный бит данных, введенный в кодер в момент времени t, равен нулю, причем бит данных является m-ым битом из k битов данных, и для формирования программируемого выходного результата в качестве функции указанной вероятности.
10. A decoder for a trellis code with a finite sequence of bits generated by the encoder, characterized in that said decoder provides decoding by determining the joint probability that the encoder state S t at time t is m, and that the received sequence of L output signals of channels having values Y L l = {y l , ..., y L }, which corresponds to λ t (m) = P {S t = m; Y L l }, moreover, the said lattice code has M states of the encoder, the decoder determines L conditional probability matrices G t , one for each of the L levels of the lattice code, the elements of the said probability matrices are determined by the relation
Г t (i, j) = Р {state j at the moment of time t; y t / state i at time tl};
by determining the row vectors α t having M elements of joint probability, determined by the ratio
Figure 00000005

and by determining the column vectors β t having M conditional probability elements, defined by the ratio
Figure 00000006

for j = 0, ..., (M-1), moreover, said decoder contains calculator G t for receiving said channel output signals, channel transition probability R (Y t , X), probability p t (m / m '), that the encoder transitions from the state m 'to the state m at the moment of time t, and the probability q t (X / m', m) that the output symbol of the encoder is X provided that the previous state of the encoder is m 'and the current state the encoder is m, and to determine from the specified scalar elements of the said probability matrices G t , the calculator is the product of the matrices α t for receiving the mentioned of scalar elements Г t with calculator Г t and formation of row vectors α t , calculator of matrix products β t for forming column vectors β t , calculator element-wise
products for the formation of joint probability vectors λ t , and the said calculator is the product of matrixes α t , the calculator of the product of matrices β t and the calculator of elementwise products form the specified vectors α t , β t , λ t by
(i. a) calculations starting from the initial α 0 equal to (1 / M, ..., 1 / M), forward recursion L times in the form α t = α t-1 Г t , y = l, .. ., L and normalization of the results so that the elements of each α t sum up to unity, with all the L vectors α t being saved,
(i. b) calculations, taking α 0 equal to α L from stage (ia) and starting from the moment t = l, α t = α tl Г t , t = 1,2, ..., L w , where the depth of the cycle L w is a predetermined number of cascades of a trellis code, and normalizing the results so that the elements of each α t sum up to one, replacing α t , calculated in step (ia), by α t , calculated in step (ib), for t = 1, 2, ... L w ,
(ii. a) initialization β L = (l, l, l, ..., l) T and for the formation of the previous β t by reverse recursion in accordance with the relation
β t = Г t + 1 β t + 1 , t = Ll, ..., l;
and normalizing the results of recursion so that the elements of each β t sum up to unity, with all the L vectors β t being saved,
(ii.b) calculations, with β L + 1 equal to β l , according to step (ii.a), and with Г L + 1 equal to Г 1 , starting with t = L,
β t = Г t + 1 β t + 1 , for t = L, L-1, ..., L- (L w + l);
where the cycle depth L w is a predetermined number of cascades of a trellis code, and the rationing of the recursion results so that the elements of each β t are summed to one, with the replacement of the β t vectors calculated in step (ii.a) with β t values calculated on stage (ii.b), for t = L, Ll, .... L- (L w + l);
(iii) the formation of joint probability vectors λ t , whose elements are the above mentioned joint probabilities λ t (i, j), by multiplying the elements of the row vectors by the elements of the column vectors according to the relation
λ t (i) = α t (i) β t (i), for all x i, t = l, ..., L;
memory for storing the said probability matrices and row vectors and the probability calculator of the decoded bit value to determine from λ t the probability that the specified data bit entered into the encoder at time t is zero, and the data bit is the m-th bit of k data bits, and to generate a programmable output as a function of a specified probability.
11. Декодер по п. 10, отличающийся тем, что дополнительно содержит устройство пороговой обработки для приема значения вероятности того, что бит данных, введенный в кодер в момент времени t, равен нулю и для реализации решающего правила для формирования декодированных выходных битов. 11. The decoder according to claim 10, characterized in that it further comprises a threshold processing device for receiving a probability value that the data bit entered into the encoder at time t is zero and for implementing a decision rule for generating decoded output bits. 12. Декодер по п.10, отличающийся тем, что упомянутый решетчатый код с конечной последовательностью битов представляет собой сверточный код. 12. The decoder of claim 10, characterized in that the said lattice code with a finite sequence of bits is a convolutional code. 13. Декодер по п.10, отличающийся тем, что содержит декодер с ограниченным кодовым расстоянием. 13. The decoder of claim 10, characterized in that it contains a decoder with a limited code distance. 14. Декодер по п. 10, отличающийся тем, что кодер обеспечивает кодирование блока битов данных, причем биты данных группируются в k-битовые символы для кодирования, при этом предварительно определенное максимальное число рекурсий содержит двукратное число k-битовых входных символов в блоке битов данных. 14. The decoder according to claim 10, wherein the encoder encodes a block of data bits, the data bits are grouped into k-bit symbols for encoding, the predetermined maximum number of recursions contains twice the number of k-bit input symbols in the data bit block . 15. Способ декодирования решетчатого кода с конечной последовательностью битов, генерируемого кодером, путем определения совместной вероятности того, что состояние St кодера в момент t есть m, и что принята последовательность из L выходных сигналов каналов, имеющих значения YLl = {yl,...,yL}, что соответствует λt(m) = P{St= m; Y L l }, причем упомянутый решетчатый код имеет М состояний кодера, отличающийся тем, что включает этапы определения L матриц вероятности Гt, по одной для каждого из L уровней решетчатого кода, причем элементы упомянутых матриц вероятности определяются соотношением
Гt(i, j) = Р{состояние j в момент времени t-l; yt/состояние i в момент времени t-l};
определения векторов-строк αt, имеющих М элементов совместной вероятности, определяемых соотношением
Figure 00000007

и определения векторов-столбцов βt, имеющих М элементов условной вероятности, определяемых соотношением
Figure 00000008

для j=0,...,(М-1), причем этапы указанного способа включают
определение скалярных элементов упомянутых матриц вероятности Гt из упомянутых выходных сигналов канала, вероятности перехода канала R(Yt,X), вероятности pt(m/m'), что кодер осуществляет переход из состояния m' в состояние m в момент времени t, и вероятности qtX/m',m) того, что выходной символ кодера есть Х при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера есть m, вычисление произведения матриц Г1 Г1,...,ГL из упомянутых скалярных элементов Гt, вычисление нормированного собственного вектора α0, соответствующего наибольшему собственному значению P{YLl} упомянутого произведения матриц Г1 Г1,...,ГL, формирование последующего значения αt путем прямой рекурсии в соответствии с выражением
αt= αt-1Гt, y = l,...,L;
формирование векторов-столбцов путем инициализации βL= (l, l,l,...,l)T и формирование предыдущего βt путем обратной рекурсии в соответствии с соотношением
βt= Гt+1βt+1, t = L-l,...,l;
формирование векторов совместной вероятности λt, элементы которой являются упомянутыми совместными вероятностями λt(i,j), путем умножения элементов векторов-строк на элементы векторов-столбцов согласно соотношению
λt(i) = αt(i)βt(i), для всеx i, t = l,...,L;
и определение из λt вероятности того, что заданный бит данных, введенный в кодер в момент времени t, равен нулю, причем бит данных является m-ым битом из k битов данных, и формирование программируемого выходного результата в качестве функции указанной вероятности.
15. A method for decoding a trellis code with a finite sequence of bits generated by the encoder by determining the joint probability that the encoder state S t at time t is m, and that the sequence of L output signals of the channels having the values Y L l = {y l , ..., y L }, which corresponds to λ t (m) = P {S t = m; Y L l }, moreover, said lattice code has M states of an encoder, characterized in that it includes the steps of determining L probability matrices Γ t , one for each of L lattice code levels, and the elements of said probability matrices are determined by the relation
Г t (i, j) = Р {state j at the moment of time tl; y t / state i at time tl};
definitions of row vectors α t having M elements of joint probability, determined by the ratio
Figure 00000007

and determining column vectors β t having M conditional probability elements, defined by the ratio
Figure 00000008

for j = 0, ..., (M-1), and the steps of this method include
determination of scalar elements of said probability matrices G t from said channel output signals, channel transition probability R (Y t , X), probability p t (m / m ′) that the encoder transitions from state m ′ to state m at time t , and the probabilities q t X / m ', m) that the output symbol of the encoder is X provided that the previous state of the encoder is m' and the current state of the encoder is m, the calculation of the product of the matrices G 1 G 1 , ..., t L of said scalar elements t t, the calculation of the normalized eigenvector α 0 corresponding to the most Shem eigenvalue P {Y L l} of said matrix product r 1 r 1, ..., G L, the formation of subsequent values α t by the forward recursion in accordance with the expression
α t = α t-1 G t , y = l, ..., L;
the formation of column vectors by initializing β L = (l, l, l, ..., l) T and the formation of the previous β t by reverse recursion in accordance with the ratio
β t = Г t + 1 β t + 1 , t = Ll, ..., l;
formation of joint probability vectors λ t , whose elements are the mentioned joint probabilities λ t (i, j), by multiplying the elements of the row vectors by the elements of the column vectors according to the relation
λ t (i) = α t (i) β t (i), for all x i, t = l, ..., L;
and determining from λ t the probability that the specified data bit entered into the encoder at time t is zero, the data bit being the m-th bit of the k data bits, and generating a programmed output as a function of the specified probability.
16. Способ по п. 15, отличающийся тем, что дополнительно включает этап осуществления решающего правила для формирования декодированных выходных битов исходя из вероятности того, что бит данных, введенный в кодер в момент времени t, равен нулю. 16. The method of claim 15, further comprising the step of implementing a decision rule for generating decoded output bits based on the probability that the data bit entered into the encoder at time t is zero. 17. Способ по п. 15, отличающийся тем, что упомянутый решеточный код с конечной последовательностью битов представляет собой сверточный код. 17. The method according to p. 15, characterized in that the said lattice code with a finite sequence of bits is a convolutional code. 18. Способ декодирования решетчатого кода с конечной последовательностью битов, генерируемого кодером, путем определения совместной вероятности того, что состояние St кодера в момент t есть m, и что принята последовательность из L выходных сигналов каналов, имеющих значения YLl = {yl,...,yL}, что соответствует λt(m) = P{St= m; Y L l }, причем упомянутый решетчатый код имеет М состояний кодера, отличающийся тем, что включает этапы определения L матриц вероятности Гt, по одной для каждого из L уровней решетчатого кода, причем элементы упомянутых матриц вероятности определяются соотношением
Гt(i, j) = Р{состояние j в момент времени t-l; yt/состояние i в момент времени t-l};
определения векторов-строк αt, имеющих М элементов совместной вероятности, определяемых соотношением
Figure 00000009

и определения векторов-столбцов βt, имеющих М элементов условной вероятности, определяемых соотношением
Figure 00000010

для j = 0,...,(М-1), причем этапы указанного способа включают
определение скалярных элементов упомянутых матриц вероятности Гt из упомянутых выходных сигналов канала, вероятности перехода канала R(Yt,X), вероятности pt(m/m'), что кодер осуществляет переход из состояния m' в состояние m в момент времени t, и вероятности qt(X/m',m) того, что выходной символ кодера есть Х при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера есть m, формирование указанных вектора αttt соответственно путем
(i.a) вычисления, начиная с начального α0, равного (1/M, ..., 1/M), рекурсии вперед L раз в виде αt= αt-1Гt, t = l,...,L и нормирования результатов так, чтобы элементы каждого нового αt суммировались до единицы, с сохранением всех L векторов αt,
(i. b) вычисления, принимая α0 равным αL из этапа (i.a) и начиная с момента t = l, αt= αt-lГt, t = 1,2,...,Lw min, где Lw min - предварительно определенное минимальное число каскадов решетчатого кода, и нормирования результатов так, чтобы элементы каждого αt суммировались до единицы, с сохранением только самого последнего множества из L векторов α, найденных путем рекурсивного вычисления согласно этапам (i.a) и (i.b), и αLw min, найденного на этапе (i.a),
(ii. с) сравнения αLw min, полученного на этапе (i.b), с αLw min, полученным на этапе (i.a), и перехода, при нахождении в пределах поля допуска, к этапу (ii), или продолжения обработки, в противном случае, на этапе (i.d),
(i. d) вычисления при t = t + 1 αt= αt-1Гt, нормирования результатов итерации так, чтобы элементы каждого αt суммировались до единицы, с сохранением только самого последнего множества из L вычисленных векторов α и данного αt, найденного на этапе (i.a),
(i.e) сравнения значений αt с самыми последними αt, вычисленными на этапах (i.a), (i.b), (i.d), и перехода, при нахождении в пределах поля допуска, к этапу (ii), или продолжения обработки на этапе (i.d), если два самых последних вектора не совпадают в пределах поля допуска и если число рекурсий не превысило определенный максимум, и перехода к этапу (ii) в противном случае,
(ii) инициализации βL= (l, l,l,...,l)T и формирования предыдущего βt путем обратной рекурсии в соответствии с соотношением
βt= Гt+1βt+1, t = L-l,...,l;
и нормирования результатов рекурсии так, чтобы элементы каждого βt суммировались до единицы, с сохранением всех L векторов βt,
(iii) формирования векторов совместной вероятности λt, элементы которой являются упомянутыми совместными вероятностями λt(i,j), путем умножения элементов векторов-строк на элементы векторов-столбцов согласно соотношению
λt(i) = αt(i)βt(i), для всеx i, t = l,...,L;
и определение из λt вероятности того, что заданный бит данных, введенный в кодер в момент времени t, равен нулю, причем бит данных является m-ым битом из k битов данных, и формирование программируемого выходного результата в качестве функции указанной вероятности.
18. A method for decoding a trellis code with a finite sequence of bits generated by the encoder by determining the joint probability that the encoder state S t at time t is m, and that the sequence of L output signals of channels having the values Y L l = {y l , ..., y L }, which corresponds to λ t (m) = P {S t = m; Y L l }, moreover, said lattice code has M states of an encoder, characterized in that it includes the steps of determining L probability matrices Γ t , one for each of L lattice code levels, and the elements of said probability matrices are determined by the relation
Г t (i, j) = Р {state j at the moment of time tl; y t / state i at time tl};
definitions of row vectors α t having M elements of joint probability, determined by the ratio
Figure 00000009

and determining column vectors β t having M conditional probability elements, defined by the ratio
Figure 00000010

for j = 0, ..., (M-1), and the steps of this method include
determination of scalar elements of said probability matrices G t from said channel output signals, channel transition probability R (Y t , X), probability p t (m / m ′) that the encoder transitions from state m ′ to state m at time t , and the probabilities q t (X / m ', m) of the fact that the output symbol of the encoder is X provided that the previous state of the encoder is m' and the current state of the encoder is m, the formation of the indicated vector α t , β t , λ t respectively by
(ia) calculations, starting from the initial α 0 , equal to (1 / M, ..., 1 / M), forward recursion L times in the form α t = α t-1 Г t , t = l, ..., L and normalization of the results so that the elements of each new α t sum up to unity, with all the L vectors α t being saved,
(i. b) calculations, taking α 0 equal to α L from stage (ia) and starting from the moment t = l, α t = α tl Г t , t = 1,2, ..., L w min , where L w min is the predetermined minimum number of cascades of a trellis code, and normalization of the results so that the elements of each α t sum up to one, while retaining only the most recent set of L vectors α, found by recursive calculation according to steps (ia) and (ib), and α Lw min found in step (ia),
(ii. c) comparing α Lw min obtained in step (ib) with α Lw min obtained in step (ia) and the transition, if within the tolerance field, to step (ii), or continuing processing, in otherwise, at the (id) stage,
(i. d) calculations at t = t + 1 α t = α t-1 Г t , normalizing the results of the iteration so that the elements of each α t sum up to one, with only the most recent set of L calculated vectors α and this α preserved t found in step (ia)
(ie) comparing the values of α t with the most recent α t , calculated in steps (ia), (ib), (id), and the transition, while within the tolerance field, to step (ii), or continuing processing in step ( id) if the two most recent vectors do not coincide within the tolerance range and if the number of recursions did not exceed a certain maximum, and go to step (ii) otherwise,
(ii) initialization β L = (l, l, l, ..., l) T and formation of the previous β t by reverse recursion in accordance with the relation
β t = Г t + 1 β t + 1 , t = Ll, ..., l;
and normalizing the results of recursion so that the elements of each β t sum up to unity, with all the L vectors β t being saved,
(iii) the formation of joint probability vectors λ t , whose elements are the above mentioned joint probabilities λ t (i, j), by multiplying the elements of the row vectors by the elements of the column vectors according to the relation
λ t (i) = α t (i) β t (i), for all x i, t = l, ..., L;
and determining from λ t the probability that the specified data bit entered into the encoder at time t is zero, the data bit being the m-th bit of the k data bits, and generating a programmed output as a function of the specified probability.
19. Способ по п. 18, отличающийся тем, что дополнительно включает этап осуществления решающего правила для формирования декодированных выходных битов, исходя из вероятности того, что бит данных, введенный в кодер в момент времени t, равен нулю. 19. The method according to p. 18, characterized in that it further includes the step of implementing a decision rule for generating decoded output bits, based on the probability that the data bit entered into the encoder at time t is zero. 20. Способ по п. 18, отличающийся тем, что упомянутый решеточный код с конечной последовательностью битов представляет собой сверточный код. 20. The method according to p. 18, characterized in that the said lattice code with a finite sequence of bits is a convolutional code. 21. Способ по п. 18, отличающийся тем, что кодер обеспечивает кодирование блока битов данных, биты данных группируются в k-битовые символы для кодирования, причем предварительно определенное максимальное число рекурсий содержит двукратное число k-битовых входных символов в блоке битов данных. 21. The method of claim 18, wherein the encoder provides encoding of a block of data bits, the data bits are grouped into k-bit symbols for encoding, with the predetermined maximum number of recursions containing twice the number of k-bit input symbols in the data bit block. 22. Способ декодирования решетчатого кода с конечной последовательностью битов, генерируемого кодером, путем определения совместной вероятности того, что состояние St кодера в момент t есть m, и что принята последовательность из L выходных сигналов каналов, имеющих значения YLl = {y1....,yL}, что соответствует λt(m) = P{St = m; Y L l }, причем упомянутый решетчатый код имеет М состояний кодера, отличающийся тем, что включает этапы определения L матриц вероятности Гt, по одной для каждого из L уровней решетчатого кода, причем элементы упомянутых матриц вероятности определяются соотношением
Гt(i, j) = Р{состояние j в момент времени t-l; yt/состояние i в момент времени t-l};
определения векторов-строк αt, имеющих М элементов совместной вероятности, определяемых соотношением
Figure 00000011

и определения векторов-столбцов βt, имеющих М элементов условной вероятности, определяемых соотношением
Figure 00000012

для j = 0,...,(M-1), причем этапы указанного способа включают
определение скалярных элементов упомянутых матриц вероятности Гt из упомянутых выходных сигналов канала, вероятности перехода канала R(Yt,X), вероятности pt(m/m'), что кодер осуществляет переход из состояния m' в состояние m в момент времени t, и вероятности qt(X/m',m) того, что выходной символ кодера есть Х при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера есть m, формирование указанных векторов αttt путем
(i. a) вычисления, начиная с начального α0, равного (1/М, ..., 1/М), рекурсии вперед L раз в виде αt= αt-1Гt, t = l,...,L и нормирования результатов так, чтобы элементы каждого αt суммировались до единицы, с сохранением всех L векторов αt,
(i.b) вычисления, принимая α0 равным αL из этапа (i.a) и начиная с момента t = l, αt= αt-lГt, t = 1,2,...,Lw, где глубина цикла Lw представляет собой предварительно определенное число каскадов решетчатого кода, и нормирования результатов так, чтобы элементы каждого αt суммировались до единицы, заменяя αt, вычисленные на этапе (i.a), на αt, вычисленные на этапе (i.b), для t = 1, 2,...Lw,
(ii. а) инициализации βL= (l, l,l,...,l)T и формирования предыдущего βt путем обратной рекурсии в соответствии с соотношением
βt= Гt+1βt+1, t = L-l,...,l;
и нормирования результатов рекурсии так, чтобы элементы каждого βt суммировались до единицы, с сохранением всех L векторов βt,
(ii.b) вычисления, при βL+1 равном βl, согласно этапу (ii.a), и при ГL+1 равном Г1, начиная с t = L,
βt= Гt+lβt+1, для t = L,L-1,...,L-(Lw+1);
где глубина цикла Lw представляет собой предварительно определенное число каскадов решетчатого кода, и нормирования результатов так, чтобы элементы каждого βt суммировались до единицы, с заменой векторов βt, вычисленных на этапе (ii.а), значениями βt, вычисленными на этапе (ii.b), для t = L,L-1,...,L-(Lw+1);
(iii) формирования векторов совместной вероятности λt, элементы которой являются упомянутыми совместными вероятностями λt(i,j), путем умножения элементов векторов-строк на элементы векторов-столбцов согласно соотношению
λt(i) = αt(i)βt(i), для всеx i, t = l,...,L;
и определение из λt вероятности того, что заданный бит данных, введенный в кодер в момент времени t, равен нулю, причем бит данных является m-ым битом из k битов данных, и формирование программируемого выходного результата в качестве функции указанной вероятности.
22. A method for decoding a trellis code with a finite sequence of bits generated by the encoder by determining the joint probability that the encoder state S t at time t is m, and that the sequence of L output signals of the channels having the values Y L l = {y 1 ...., y L }, which corresponds to λ t (m) = P {S t = m; Y L l }, moreover, said lattice code has M states of an encoder, characterized in that it includes the steps of determining L probability matrices Γ t , one for each of L lattice code levels, and the elements of said probability matrices are determined by the relation
Г t (i, j) = Р {state j at the moment of time tl; y t / state i at time tl};
definitions of row vectors α t having M elements of joint probability, determined by the ratio
Figure 00000011

and determining column vectors β t having M conditional probability elements, defined by the ratio
Figure 00000012

for j = 0, ..., (M-1), and the steps of this method include
determination of scalar elements of said probability matrices G t from said channel output signals, channel transition probability R (Y t , X), probability p t (m / m ′) that the encoder transitions from state m ′ to state m at time t , and the probabilities q t (X / m ', m) of the fact that the output symbol of the encoder is X provided that the previous state of the encoder is m' and the current state of the encoder is m, the formation of the indicated vectors α t , β t , λ t by
(i. a) calculations starting from the initial α 0 equal to (1 / M, ..., 1 / M), forward recursion L times in the form α t = α t-1 Г t , t = l, .. ., L and normalization of the results so that the elements of each α t sum up to unity, with all the L vectors α t being saved,
(ib) calculations, taking α 0 equal to α L from stage (ia) and starting from the moment t = l, α t = α tl Г t , t = 1,2, ..., L w , where the depth of the cycle is L w represents a predetermined number of cascades of a trellis code, and normalizing the results so that the elements of each α t sum up to one, replacing α t , calculated in step (ia), by α t , calculated in step (ib), for t = 1, 2, ... L w ,
(ii. a) initialization β L = (l, l, l, ..., l) T and forming the previous β t by reverse recursion in accordance with the relation
β t = Г t + 1 β t + 1 , t = Ll, ..., l;
and normalizing the results of recursion so that the elements of each β t sum up to unity, with all the L vectors β t being saved,
(ii.b) calculations, with β L + 1 equal to β l , according to step (ii.a), and with Г L + 1 equal to Г 1 , starting with t = L,
β t = Г t + l β t + 1 , for t = L, L-1, ..., L- (L w +1);
where the cycle depth L w is a predetermined number of cascades of a trellis code, and normalizing the results so that the elements of each β t are summed to one, with the replacement of the vectors β t calculated at step (ii.a) with values of β t calculated at step (ii.b), for t = L, L-1, ..., L- (L w +1);
(iii) the formation of joint probability vectors λ t , whose elements are the above mentioned joint probabilities λ t (i, j), by multiplying the elements of the row vectors by the elements of the column vectors according to the relation
λ t (i) = α t (i) β t (i), for all x i, t = l, ..., L;
and determining from λ t the probability that the specified data bit entered into the encoder at time t is zero, the data bit being the m-th bit of the k data bits, and generating a programmed output as a function of the specified probability.
23. Способ по п.22, отличающийся тем, что дополнительно включает этап осуществления решающего правила для формирования декодированных выходных битов, исходя из вероятности того, что бит данных, введенный в кодер в момент времени t, равен нулю. 23. The method of claim 22, further comprising the step of implementing a decision rule for generating decoded output bits, based on the probability that the data bit entered into the encoder at time t is zero. 24. Способ по п.22, отличающийся тем, что упомянутый решеточный код с конечной последовательностью битов представляет собой сверточный код. 24. The method according to p. 22, characterized in that the said lattice code with a finite sequence of bits is a convolutional code. 25. Способ по п.22, отличающийся тем, что кодер обеспечивает кодирование блока битов данных, биты данных сгруппированы в k-битовые символы для кодирования, а предварительно определенное максимальное число рекурсий содержит двукратное число k-битовых входных символов в блоке битов данных. 25. The method according to p. 22, wherein the encoder provides the encoding of a block of data bits, the data bits are grouped into k-bit symbols for encoding, and the predetermined maximum number of recursions contains twice the number of k-bit input symbols in the data bit block.
RU98100587/09A 1996-04-19 1997-04-14 Optimum decoder of programmable output data for lattice codes with final bit train RU2179367C2 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US08/636,742 1996-04-19
US08/636,742 US5721746A (en) 1996-04-19 1996-04-19 Optimal soft-output decoder for tail-biting trellis codes

Publications (2)

Publication Number Publication Date
RU98100587A true RU98100587A (en) 1999-12-27
RU2179367C2 RU2179367C2 (en) 2002-02-10

Family

ID=24553142

Family Applications (1)

Application Number Title Priority Date Filing Date
RU98100587/09A RU2179367C2 (en) 1996-04-19 1997-04-14 Optimum decoder of programmable output data for lattice codes with final bit train

Country Status (21)

Country Link
US (1) US5721746A (en)
EP (1) EP0834223A1 (en)
JP (1) JP3801211B2 (en)
KR (1) KR100531584B1 (en)
CN (1) CN1132320C (en)
AR (1) AR006722A1 (en)
AU (1) AU716761B2 (en)
BR (1) BR9702311A (en)
CA (1) CA2221137C (en)
CZ (1) CZ296383B6 (en)
HU (1) HU220832B1 (en)
ID (1) ID17231A (en)
IL (1) IL122526A (en)
MX (1) MX9710511A (en)
MY (1) MY125447A (en)
NO (1) NO975967L (en)
PL (1) PL182511B1 (en)
RU (1) RU2179367C2 (en)
UA (1) UA42841C2 (en)
WO (1) WO1997040583A1 (en)
ZA (1) ZA973213B (en)

Families Citing this family (57)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6377610B1 (en) * 1997-04-25 2002-04-23 Deutsche Telekom Ag Decoding method and decoding device for a CDMA transmission system for demodulating a received signal available in serial code concatenation
US5983384A (en) * 1997-04-21 1999-11-09 General Electric Company Turbo-coding with staged data transmission and processing
US6256764B1 (en) * 1997-11-26 2001-07-03 Nortel Networks Limited Method and system for decoding tailbiting convolution codes
US6452985B1 (en) * 1998-03-18 2002-09-17 Sony Corporation Viterbi decoding apparatus and Viterbi decoding method
US6563877B1 (en) * 1998-04-01 2003-05-13 L-3 Communications Corporation Simplified block sliding window implementation of a map decoder
CA2234006C (en) * 1998-04-06 2004-10-19 Wen Tong Encoding and decoding methods and apparatus
TW377427B (en) * 1998-05-26 1999-12-21 Koninklijke Philips Electronics Nv Transmission system having a simplified channel decoder applicable to mobile phone systems for better reliability in serial transmission
WO1999062183A1 (en) * 1998-05-28 1999-12-02 Sony Corporation Soft output decoder for convolution code and soft output decoding method
US6192501B1 (en) 1998-08-20 2001-02-20 General Electric Company High data rate maximum a posteriori decoder for segmented trellis code words
US6223319B1 (en) 1998-08-20 2001-04-24 General Electric Company Turbo code decoder with controlled probability estimate feedback
US6128765A (en) * 1998-08-20 2000-10-03 General Electric Company Maximum A posterior estimator with fast sigma calculator
US6263467B1 (en) 1998-08-20 2001-07-17 General Electric Company Turbo code decoder with modified systematic symbol transition probabilities
WO2000019616A2 (en) 1998-09-28 2000-04-06 Advanced Hardware Architectures, Inc. Turbo product code decoder
EP1099313B1 (en) 1998-12-01 2004-04-07 Siemens Aktiengesellschaft Soft decision decoding of a scheduled convolutional code
US6088405A (en) * 1999-01-15 2000-07-11 Lockheed Martin Corporation Optimal decoder for tall-biting convolutional codes
US6304996B1 (en) * 1999-03-08 2001-10-16 General Electric Company High-speed turbo decoder
US6715120B1 (en) 1999-04-30 2004-03-30 General Electric Company Turbo decoder with modified input for increased code word length and data rate
US6594792B1 (en) 1999-04-30 2003-07-15 General Electric Company Modular turbo decoder for expanded code word length
US6877132B1 (en) 1999-06-11 2005-04-05 Nortel Network Limited Method and apparatus for channel decoding of tail-biting convolutional codes
US7277506B1 (en) * 1999-08-09 2007-10-02 Broadcom Corporation Maximum likelihood sequence estimator which computes branch metrics in real time
US6400290B1 (en) 1999-11-29 2002-06-04 Altera Corporation Normalization implementation for a logmap decoder
US6700937B1 (en) * 2000-01-05 2004-03-02 At&T Corp. Iterative decoding
US7092457B1 (en) * 2000-01-18 2006-08-15 University Of Southern California Adaptive iterative detection
KR100374787B1 (en) * 2000-01-18 2003-03-04 삼성전자주식회사 Bandwidth-efficient concatenated trellis-coded modulation decoder and method thereof
US6810502B2 (en) * 2000-01-28 2004-10-26 Conexant Systems, Inc. Iteractive decoder employing multiple external code error checks to lower the error floor
US6484285B1 (en) * 2000-02-07 2002-11-19 Ericsson, Inc. Tailbiting decoder and method
US6580769B1 (en) * 2000-02-14 2003-06-17 Motorola, Inc. Method and apparatus for backward recursion next state generation in recursive convolutional decoding
GB0004765D0 (en) * 2000-03-01 2000-04-19 Mitel Corp Soft-decision decoding of convolutionally encoded codeword
US6516437B1 (en) 2000-03-07 2003-02-04 General Electric Company Turbo decoder control for use with a programmable interleaver, variable block length, and multiple code rates
US7356752B2 (en) * 2000-03-14 2008-04-08 Comtech Telecommunications Corp. Enhanced turbo product codes
GB2360858B (en) * 2000-03-20 2004-08-18 Motorola Inc High-speed maximum a posteriori (MAP) architecture with optimized memory size and power consumption
EP1281241A2 (en) * 2000-04-04 2003-02-05 Advanced Hardware Architectures, Inc Enhanced turbo product code decoder system
JP4543522B2 (en) * 2000-08-31 2010-09-15 ソニー株式会社 Soft output decoding device, soft output decoding method, and decoding device and decoding method
IT1320715B1 (en) * 2000-10-19 2003-12-10 Cselt Centro Studi Lab Telecom CIRCUIT GENERATOR MODULE FOR THE DECODING OF CONVENTIONAL CODES, METHOD FOR THE GENERATION OF SUCH TYPE OF CIRCUIT AND
US7230978B2 (en) 2000-12-29 2007-06-12 Infineon Technologies Ag Channel CODEC processor configurable for multiple wireless communications standards
US7010052B2 (en) * 2001-04-16 2006-03-07 The Ohio University Apparatus and method of CTCM encoding and decoding for a digital communication system
WO2002091592A1 (en) * 2001-05-09 2002-11-14 Comtech Telecommunications Corp. Low density parity check codes and low density turbo product codes
US6763493B2 (en) * 2001-09-21 2004-07-13 The Directv Group, Inc. Method and system for performing decoding using a reduced-memory implementation
JP3549519B2 (en) * 2002-04-26 2004-08-04 沖電気工業株式会社 Soft output decoder
US7346833B2 (en) * 2002-11-05 2008-03-18 Analog Devices, Inc. Reduced complexity turbo decoding scheme
GB2403103A (en) * 2003-06-16 2004-12-22 Inmarsat Ltd Multi-user detection and decoding
RU2339161C2 (en) * 2004-03-22 2008-11-20 Мацусита Электрик Индастриал Ко., Лтд. Map decoder of local erasure
US7062407B2 (en) * 2004-09-13 2006-06-13 Microsoft Corporation Efficient backward recursion for computing posterior probabilities
US7603613B2 (en) * 2005-02-17 2009-10-13 Samsung Electronics Co., Ltd. Viterbi decoder architecture for use in software-defined radio systems
US7627064B2 (en) * 2006-06-30 2009-12-01 Intel Corporation System and method for enhanced symbol generation
RU2340088C2 (en) * 2006-11-23 2008-11-27 Андрей Николаевич Хмельков Syndrome decoding method of decoding recurrent code (versions)
WO2008075125A1 (en) * 2006-12-20 2008-06-26 Wavesat Inc. Method and decoder for tail-biting decoding
US8358713B2 (en) * 2007-09-10 2013-01-22 Sarath Babu Govindarajulu High throughput and low latency map decoder
US8219896B2 (en) * 2007-10-23 2012-07-10 Telefonaktiebolaget L M Ericsson (Publ) Reduced-complexity decoding algorithms for tail-biting convolutional codes
JP4806673B2 (en) * 2007-12-27 2011-11-02 ルネサスエレクトロニクス株式会社 Decoding device and decoding method
US8392811B2 (en) * 2008-01-07 2013-03-05 Qualcomm Incorporated Methods and systems for a-priori decoding based on MAP messages
RU2390930C2 (en) * 2008-04-21 2010-05-27 Государственное образовательное учреждение высшего профессионального образования Курский государственный технический университет Ptcm decoder
US20090271686A1 (en) * 2008-04-28 2009-10-29 Qualcomm Incorporated Communication signal decoding with iterative cooperation between turbo and reed-solomon decoding
EP2114013B1 (en) 2008-04-30 2010-08-04 TELEFONAKTIEBOLAGET LM ERICSSON (publ) Method and arrangement for decoding a signal encoded by a tail-biting code
US8924811B1 (en) * 2010-01-12 2014-12-30 Lockheed Martin Corporation Fast, efficient architectures for inner and outer decoders for serial concatenated convolutional codes
GB2559616A (en) * 2017-02-13 2018-08-15 Accelercomm Ltd Detection circuit, receiver, communications device and method of detecting
RU2706171C1 (en) * 2019-01-25 2019-11-14 Федеральное государственное казенное военное образовательное учреждение высшего образования Академия Федеральной службы охраны Российской Федерации Method for decoding block noise-immune codes based on the criterion of minimum average risk

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
RU2022469C1 (en) * 1990-07-02 1994-10-30 Научно-исследовательский институт "Дельта" Multichannel decoding device
FR2675968B1 (en) * 1991-04-23 1994-02-04 France Telecom METHOD FOR DECODING A CONVOLUTIVE CODE WITH MAXIMUM LIKELIHOOD AND WEIGHTING OF DECISIONS, AND CORRESPONDING DECODER.
US5349589A (en) * 1991-07-01 1994-09-20 Ericsson Ge Mobile Communications Inc. Generalized viterbi algorithm with tail-biting
US5369671A (en) * 1992-05-20 1994-11-29 Hughes Aircraft Company System and method for decoding tail-biting code especially applicable to digital cellular base stations and mobile units
US5355376A (en) * 1993-02-11 1994-10-11 At&T Bell Laboratories Circular viterbi decoder
US5577053A (en) * 1994-09-14 1996-11-19 Ericsson Inc. Method and apparatus for decoder optimization

Similar Documents

Publication Publication Date Title
RU98100587A (en) OPTIMAL DECODER PROGRAMMABLE DETAILS FOR GRIDED CODES WITH FINITE SEQUENCE BITS
RU2179367C2 (en) Optimum decoder of programmable output data for lattice codes with final bit train
US6476740B1 (en) Z-coder: a fast adaptive binary arithmetic coder
US6225925B1 (en) Z-coder: a fast adaptive binary arithmetic coder
Gray et al. Vector quantizers and predictive quantizers for Gauss-Markov sources
Willems et al. Context weighting for general finite-context sources
US6263467B1 (en) Turbo code decoder with modified systematic symbol transition probabilities
US6128765A (en) Maximum A posterior estimator with fast sigma calculator
US7903766B2 (en) Iterative decoding
US6223319B1 (en) Turbo code decoder with controlled probability estimate feedback
US7263652B2 (en) Maximum likelihood detector and/or decoder
GB2315001A (en) Viterbi decoder for depunctured codes
Frey et al. Efficient stochastic source coding and an application to a Bayesian network source model
US6259388B1 (en) Multiplication-free arithmetic coding
Sitaram et al. Efficient codebooks for vector quantization image compression with an adaptive tree search algorithm
Aksu et al. Multistage trellis coded quantisation (MS-TCQ) design and performance
US6622145B2 (en) Huffman coding for infinite symbol sets
CN100417030C (en) Signal processing method using approximate MAP algorithm and communication signal receiver
Lee A very efficient transfer function bounding technique on bit error rate for Viterbi decoded, rate 1/N convolutional codes
RU2752868C1 (en) Method for arithmetic encoding and decoding
EP1678833A2 (en) Resilient parameterized prefix codes for adaptive coding
Lahouti et al. Sequence MMSE source decoding over noisy channels using the residual redundancies
Larsen et al. Complexity-constrained trellis quantizers
Handlery et al. Distance Approach to Window Decoding
KR100332748B1 (en) Vector quantization search method of speech recognition