Decomposer for parallel turbo decoding, process and integrated circuit
A decoder for access data stored in n memories comprises a function matrix containing addresses of the memory locations at unique coordinates. A decomposer sorts addresses from coordinate locations of first and second m×n matrices, such that each row contains no more than one address from the same memory. Positional apparatus stores entries in third and fourth m×n matrices identifying coordinates of addresses in the function matrix such that each entry in the third matrix is at coordinates that matches corresponding coordinates in the first matrix, and each entry in the fourth matrix is at coordinates that matches corresponding coordinates in the second matrix. The decoder is responsive to entries in the matrices for accessing data in parallel from the memories.
1 . A decomposer for decomposing at least a set of parallel concatenated convolutional codes representing addresses in a plurality of memories, the set of codes being arranged at coordinates in a function matrix table, the decomposer comprising:
first and second matrix tables, each having m rows and n columns defining coordinates, each of the first and second tables containing the codes at coordinates such that each row contains no more than one code of a respective group of the codes; and
third and fourth matrix tables, each having m rows and n columns, and containing entries identifying coordinates in the function matrix table and arranged so that each entry in the third matrix table is at coordinates that match coordinates in the first matrix table containing the corresponding code, and each entry in the fourth matrix table is at coordinates that match coordinates in the second matrix table containing the corresponding code.
2 . The decomposer of claim 1 , wherein the set of codes in the function matrix table represents a function f:{0, 1, 2, 3, . . . , n*m−1)→f:{0, 1, 2, 3, . . . , 2 k −1}.
3 . The decomposer of claim 1 , further including:
an organizer for organizing the addresses into first and second sets, S r q , each containing the addresses, and
a sorter for sorting the first set of addresses into the first matrix table and sorting the second set of addresses into the second matrix table.
4 . The decomposer of claim 3 , wherein the organizer includes:
an edge identifier for identifying a plurality of edges between the addresses such that each edge contains two addresses, and each address is unconnected or in not more than two edges,
a linker for linking the edges into a sequence, and
an assignor for alternately assigning edges to first and second sets.
5 . The decomposer of claim 4 , wherein the sorter includes, for each set:
a divider for dividing each set, S r q , of addresses into first and second subsets S r+1 2q and S r+1 2q+1 ,
placer apparatus for placing the first and second subsets into respective rows of the respective first and second matrix table, and
iteration apparatus for iteratively repeating operation of the divider and placer until each row contains no more than one address of a location in each respective memory.
6 . The decomposer of claim 3 , wherein the sorter includes, for each set:
a divider for dividing each set, S r q , of addresses into first and second subsets S r+1 2q and S r+1 2q+1 ,
placer apparatus for placing the first and second subsets into respective rows of the respective first and second matrix table, and
iteration apparatus for iteratively repeating operation of the divider and placer until each row contains no more than one address of a location in each respective memory.
7 . The decomposer of claim 1 wherein the first, second, third and fourth matrix tables are implemented at least in part in at least one integrated circuit.
8 . A decomposer for decomposing at least a set of parallel concatenated convolutional codes representing addresses in a plurality of memories, the set of codes being arranged at coordinates in a function matrix implemented at least in part in at least one integrated circuit, the decomposer comprising:
first and second matrices implemented at least in part in at least one integrated circuit, each of the first and second matrices having m rows and n columns defining coordinates, each of the first and second tables containing the codes at coordinates such that each row contains no more than one code of a respective group of the codes; and
third and fourth matrices implemented at least in part in at least one integrated circuit, each of the third and fourth matrices having m rows and n columns, and containing entries identifying coordinates in the function matrix and arranged so that each entry in the third matrix is at coordinates that match coordinates in the first matrix containing the corresponding code, and each entry in the fourth matrix is at coordinates that match coordinates in the second matrix containing the corresponding code.
9 . The decomposer of claim 1 , wherein the set of codes in the function matrix represents a function f:{0, 1, 2, 3, . . . , n*m−1)→f:{0, 1, 2, 3, . . . , 2 k −1}.
10 . The decomposer of claim 8 , further including:
an organizer for organizing the addresses into first and second sets, S r q , each containing the addresses, and
a sorter for sorting the first set of addresses into the first matrix and sorting the second set of addresses into the second matrix.
11 . The decomposer of claim 10 , wherein the organizer includes:
an edge identifier for identifying a plurality of edges between the addresses such that each edge contains two addresses, and each address is unconnected or in not more than two edges,
a linker for linking the edges into a sequence, and
an assignor for alternately assigning edges to first and second sets.
12 . The decomposer of claim 11 , wherein the sorter includes, for each set:
a divider for dividing each set, S r q , of addresses into first and second subsets S r+1 2q and S r+1 2q+1 ,
placer apparatus for placing the first and second subsets into respective rows of the respective first and second matrix, and
iteration apparatus for iteratively repeating operation of the divider and placer until each row contains no more than one address of a location in each respective memory.
13 . The decomposer of claim 10 , wherein the sorter includes, for each set:
a divider for dividing each set, S r q , of addresses into first and second subsets S r+1 2q and S r+1 2q+1 ,
placer apparatus for placing the first and second subsets into respective rows of the respective first and second matrix, and
iteration apparatus for iteratively repeating operation of the divider and placer until each row contains no more than one address of a location in each respective memory.