Back to results
US 6,553,516 B1Granted
Interleaving method, interleaving apparatus, turbo encoding method, and turbo encoder
AssigneeNTT Mobile Communications Network, Inc.
InventorsHirohito Suda, Akira Shibutani
Life of this patent
Estimating the term…
Abstract
An interleaving method including the step of (1) receiving a data sequence having a plurality of blocks, each having a length based on a prime number P; (2) generating sequence permutation data by performing a given operation on elements of a Galois field of a characteristic P; (3) permuting results of the given operation, so that sequence permutation data are generated; and (4) permuting a sequence of data of the data sequence in accordance with the sequence permutation data.
Claims51
An interleaving method comprising the steps of:
- (a) generating or recording a prime number P by using K bits of an input sequence and N of rows of an interleaver;
- (b) dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to P, where N is an integer equal to at least 2;
- (c) one of generating and recording zeroth sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- (d) one of generating and recording N integers P1, P2, . . . , PN which are mutually prime with respect to a primitive root used in the power notation;
- (e) one of generating and recording first through Nth sequence permutation data by repeating, ith times (i=1−N), a process for generating ith sequence permutation data which is a sequence of values of exponent parts in power notation of elements obtained by adding qi to data of the zeroth sequence permutation data;
- (f) permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- (g) reading permuted data from the blocks B1-BN in a given order.
5 more elements
An interleaving method comprising the steps of:
- (a) one of generating and recording a prime number P by using K bits of an input sequence and N of rows of an interleaver;
- (b) dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to (P−1), where N is an integer equal to at least 2;
- (c) one of generating and recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- (d) one of generating and recording (N−1) integers P1, P2, . . . , PN−1 which are mutually prime with respect to P−1);
- (e) one of generating and recording second through Nth sequence permutation data by repeating, ith times (i=1(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of Pi,
- (f) permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- (g) reading permuted data from the blocks B1-BN in a given order.
5 more elements
An interleaving method comprising the steps of:
- (a) one of generating and recording a prime number P by using K bits of an input sequence and N of rows of an interleaver;
- (b) dividing an input sequence into N blocks B1, B2, . . . , BN, each having a length equal to (P+1), where N is an integer equal to at least 2;
- (c) one of generating and recording first sequence permutation data in which elements of a Galoid field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- (d) generating or recording (N−1) integers P1, P2, . . . , PN−1 which are mutually prime with respect to (P−1);
- (e) one of generating and recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of Pi;
- (f) permuting data in blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- (g) reading permuted data from the blocks B1-BN in a given order.
5 more elements
An interleaving apparatus comprising:
- first means for one of generating and recording a prime number P by using K bits of an input sequence and N of rows of the interleaving apparatus;
- second means for dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to P, where N is an integer equal to or greater than 2;
- third means for one of generating and recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- fourth means for one of generating and recording (N−1) integers P1, P2, . . . , PN−1 which are mutually prime with respect to (P−1);
- fifth means for one of generating and recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of Pl;
- sixth means for permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- seventh means for reading permuted data from the blocks B1-BN in a given order.
5 more elements
An interleaving apparatus comprising:
- first means for one of generating and recording a prime number P by using K bits of an input sequence and N of rows of the interleaving apparatus;
- second means for dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to P, where N is an integer equal to at least 2;
- third means for one of generating and recording zeroth sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- fourth means for one of generating and recording N integers P1, P2, . . . , PN which are mutually prime with respect to a primitive root used in the power notation;
- fifth means for one of generating and recording first through Nth sequence permutation data by repeating, ith times (i=1−N), a process for generating ith sequence permutation data, which is a sequence of values of exponent parts in power notation of elements obtained by adding qi to data of the zeroth sequence permutation data;
- sixth means for permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- seventh means for reading permuted data from the blocks B1-BN in a given order.
5 more elements
An interleaving apparatus comprising:
- first means for one of generating and recording a prime number P by using K bits of an input sequence and N of rows of the interleaving apparatus;
- second means for dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to (P−1) where N is an integer equal to at least 2;
- third means for one of generating and recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- fourth means for one of generating and recording (N−1) integers P1, P2, . . . , PN−1 which are mutually prime with respect to (P−1);
- fifth means for one of generating and recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)) a process for generating ith sequence permutation data by cyclically reading data in the first permutation data at intervals of Pi;
- sixth means for permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- seventh means for reading permuted data from the blocks B1-BN in a given order.
5 more elements
A turbo encoding method comprising, as an interleaving method employed in a turbo encoder, the interleaving method comprising the steps of:
- (a) generating or recording a prime number P;
- (b) dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to P where N is an integer equal to or greater than 2;
- (c) generating or recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- (d) generating or recording (N−1) integers p1, p2, . . . , pN-1 which are mutually prime with respect to (P−1);
- (e) generating or recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of pi;
- (f) permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- (g) reading permuted data from the blocks B1-BN in a given order.
5 more elements
A turbo encoding method comprising, as an interleaving method employed in a turbo encoder, the interleaving method comprising the steps of:
- (a) generating or recording a prime number P;
- (b) dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to P where N is an integer equal to or greater than 2;
- (c) generating or recording zeroth sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- (d) generating or recording N integers p1, p2, . . . , pN which are mutually prime with respect to a primitive root used in the power notation;
- (e) generating or recording first through Nth sequence permutation data by repeating, ith times (i=1−N), a process for generating ith sequence permutation data which is a sequence of values of exponent parts in power notation of elements obtained by adding qi to data of the zeroth sequence permutation data;
- (f) permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- (g) reading permuted data from the blocks B1-BN in a given order.
5 more elements
A turbo encoding method comprising, as an interleaving method employed in a turbo encoder, the interleaving method comprising the steps of:
- (a) generating or recording a prime number P;
- (b) dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to (P−1) where N is an integer equal to or greater than 2;
- (c) generating or recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- (d) generating or recording (N−1) integers p1, p2, . . . , pN-1 which are mutually prime with respect to (P−1);
- (e) generating or recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of p1;
- (f) permuting data in the blocks B1-BN in accordance with the firsth through Nth sequence permutation data, and
- (g) reading permuted data from the blocks B1-BN in a given order.
4 more elements
A turbo encoding method comprising, as an interleaving method employed in a turbo encoder, the interleaving method comprising the steps of:
- (a) generating or recording a prime number P;
- (b) dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to (P+1 ) where N is an integer equal to or greater than 2;
- (c) generating or recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- (d) generating or recording (N−1) inters p1, p2, . . . , pN−1 which are mutually prime with respect to (P−1);
- (e) generating or recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of pi;
- (f) permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- (g) reading permuted data from the blocks B1-BN in a given order.
5 more elements
A turbo encoder comprising:
- a plurality of encoders;
- and
- an interleaving apparatus comprising:
- first means for generating or recording a prime number P;
- second means for dividing an input sequence into N blocks B1,B2, . . . , BN each having a length equal to P, where N is an integer equal to at least 2;
- third means for one of generating and recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- fourth means for one of generating and recording (N−1) integers P1, P2, . . . , PN−1 which are mutually prime with respect to (P−1);
- fifth means for one of generating and recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of Pi;
- sixth means for permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- seventh means for reading permuted data from the blocks B1-BN in a given order.
8 more elements
A turbo encoder comprising:
- a plurality of encoders;
- and
- an interleaving apparatus comprising:
- first means for generating or recording a prime number P;
- second means for dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to P, where N is an integer equal to at least 2;
- third means for one of generating and recording zeroth sequence permutation data in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- fourth means for one of generating and recording N integers P1, P2, . . . , PN which are mutually prime with respect to a primitive root used in the power notation;
- fifth means for one of generating and recording first through Nth sequence permutation data by repeating, ith times (i=1−N), a process for generating ith sequence permutation data which is a sequence of values of exponent parts in power notation of elements obtained by adding qi to data of the zeroth sequence permutation data;
- sixth means for permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- seventh means for reading permuted data from the blocks B1-BN in a given order.
8 more elements
A turbo encoder comprising:
- a plurality of encoders;
- and
- an interleaving apparatus comprising:
- first means for generating or recording a prime number P;
- second means for dividing an input sequence into N blocks B1, B2, . . . , BN each having a length equal to (P−1) where N is an integer equal to or greater than 2;
- third means for one of generating and recording first sequence permutation data in which elements of a Galois field of a characteristic P are arranged in order of values of exponent parts of a power notation of the elements;
- fourth means for one generating and recording (N−1) integers P1, P2, . . . , PN−1 which are mutually prime with respect to (P−1);
- fifth means for one of generating and recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of Pi;
- sixth means for permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- seventh means for reading permuted data from the blocks B1-BN in a given order.
8 more elements
An interleaving method, comprising:
- one of creating and recording N rows of an interleaver for turbo encoding;
- one of generating and recording a prime number P by using K bits of an input sequence and the N rows;
- generating a two-dimensional block matrix having a length equal to any of P, P−1, P+1 and the N rows, by using the K input bits, the prime number P, and the N rows;
- inputting data having K bits into said two-dimensional matrix;
- and
- permuting said data in said two-dimensional matrix.
3 more elements
An interleaving method that interleaves K bits of data by using an interleaver having a buffer arranged in a two-dimensional matrix, comprising:
- generating a prime number P based on the K bits of data and N rows of the interleaver so that a number of columns of the interleaver is determined by the prime number P;
- permuting data in each of the N rows of the interleaver in accordance with a sequence permutation table generated specifically for each of the N rows, based on a primitive root of said prime number P;
- permuting an order of the N rows based on a predetermined inter-permutation pattern;
- and
- reading out data from the buffer in a column direction of said two-dimensional matrix.
2 more elements
An interleaver that interleaves K bits of data by using a buffer arranged in a two-dimensional matrix, comprising:
- means for generating a prime number P based on the K bits of data and N rows of the interleaver so that a number of columns of the interleaver is determined by the prime number P;
- means for permuting data in each of the N rows of the interleaver in accordance with a sequence permutation table generated specifically for each of the N rows, based on a primitive root of the prime number P;
- means for permuting an order of the N rows based on a predetermined inter-permutation pattern;
- and
- means for reading out data from the buffer in a column direction of said two-dimensional matrix.
2 more elements
A turbo encoding method in which an interleaving method is employed in a turbo encoder to interleave K bits of data by using an interleaver having a buffer arranged in a two-dimensional matrix, the interleaving method comprising the steps of:
- generating a prime number P based on the K bits of data and N rows of the interleaver so that a number of columns of the interleaver is determined by the prime number P;
- permuting data in each of the N rows of the interleaver in accordance with a sequence permutation table generated specifically for each of the N rows, based on a primitive root of said prime number P;
- permuting an order of the N rows based on a predetermined inter-permutation pattern;
- and
- reading out data from the buffer in a column direction of said two-dimensional matrix.
2 more elements
A turbo encoder, comprising:
- a plurality of encoders;
- and
- an interleaver configured to interleave K bits of data by using a buffer arranged in a two-dimensional matrix, said interleaving apparatus comprising:
- means for generating a prime number P based on the K bits of data and N rows of the interleaver so that a number of columns of the interleaver is determined by the prime number P;
- means for permuting data in each of the N rows of the interleaver in accordance with a sequence permutation table generated specifically for each of said N rows, based on a primitive root of the prime number P;
- means for permuting an order of said N rows based on a predetermined inter-permutation pattern;
- and
- means for reading out data from the buffer in a column direction of said two-dimensional matrix.
5 more elements
An interleaving method, comprising;
- (a) one of generating and recording a prime number P;
- (b) dividing an input sequence into N blocks B1, B2. . . , BN, each having a length equal to P, wherein N is an integer equal to at least one;
- (c) one of generating and recording first sequence permutation data, in which elements of a Galois field of a characteristic P are arranged in an order of values of exponent parts of a power notation of the elements;
- (d) one of generating and recording (N−1) integers p1, p2. . . , pn−1, which are mutually prime with respect to (P−1);
- (e) one of generating and recording second through Nth sequence permutation data by repeating, ith times (i=1−(N−1)), a process for generating ith sequence permutation data by cyclically reading data in the first sequence permutation data at intervals of p1;
- (f) permuting data in the blocks B1-BN in accordance with the first through Nth sequence permutation data;
- and
- (g) reading permuted data from the blocks B1-BN in a given order.
5 more elements
Dependencies are inferred from the claim text.