Parallel implementation of maximum a posteriori probability decoder
A MAP decoder may be implemented in parallel. In one implementation, a device may receive an input array that represents received encoded data and calculate, in parallel, a series of transition matrices from the input array. The device may further calculate, in parallel, products of the cumulative products of the series of transition matrices and an initialization vector. The device may further calculate, in parallel and based on the products of the cumulative products of the series of transition matrices and the initialization vector, an output array that corresponds to a decoded version of the received encoded data in the input array.
1. A method comprising:
calculating, in parallel, products of cumulative products of:
a series of transition matrices associated with an input array representing encoded data, and
an initialization vector,
the calculating the products of the cumulative products of the series of transition matrices and the initialization vector being performed by a device;
calculating, based on the products of the cumulative products of the series of transition matrices and the initialization vector, an output array that corresponds to a decoded version of the encoded data,
the calculating the output array being performed by the device; and
outputting the output array,
outputting the output array being performed by the device.
2. The method of claim 1 , where calculating the products of the cumulative products of the series of transition matrices and the initialization vector includes:
using a scan technique to convert the series of transition matrices and the initialization vector into the products of the cumulative products of the series of transition matrices and the initialization vector.
3. The method of claim 2 , where calculating the products of the cumulative products of the series of transition matrices and the initialization vector includes:
segmenting the series of transition matrices into a plurality of sections;
independently applying, as a first scan, the scan technique to each of the plurality of sections to create a series of full products;
applying, as a second scan, the scan technique to the series of the full products of the first scan of each of the plurality of sections to create partial product scan results; and
distributing the partial product scan results from the second scan of each of the plurality of sections.
4. The method of claim 1 , where calculating the products of the cumulative products of the series of transition matrices and the initialization vector includes:
performing matrix by vector multiplications before performing matrix by matrix multiplications.
5. The method of claim 1 , where calculating the products of the cumulative product of the series of transition matrices and the initialization vector includes:
implementing N/2 parallel pipelines,
where N represents a size of the input array,
where each pipeline includes K stages, and
where K corresponds to 2* log 2(N).
6. The method of claim 1 , where calculating the products of the cumulative products of the series of transition matrices and the initialization vector includes:
calculating the series of transition matrices from the input array.
7. The method of claim 1 , where values in the series of transition matrices represent probabilities associated with state transitions in a Maximum A Posteriori Probability (MAP) decoder.
8. A non-transitory computer-readable medium storing instructions, the instructions comprising:
one or more instructions that, when executed by one or more processors, cause the one or more processors to:
calculate, in parallel, products of cumulative products of:
a series of transition matrices associated with an input array representing encoded data, and
an initialization vector;
calculate, based on the products of the cumulative products of the series of transition matrices and the initialization vector, an output array that corresponds to a decoded version of the encoded data; and
output the output array.
9. The non-transitory computer-readable medium of claim 8 , where the one or more instructions to calculate the products of the cumulative products of the series of transition matrices and the initialization vector include:
one or more instructions that, when executed by the one or more processors, cause the one or more processors to use a scan technique to convert the series of transition matrices and the initialization vector into the products of the cumulative products of the series of transition matrices and the initialization vector.
10. The non-transitory computer-readable medium of claim 9 , where the one or more instructions to calculate the products of the cumulative products of the series of transition matrices and the initialization vector include:
one or more instructions that, when executed by the one or more processors, cause the one or more processors to:
segment the series of transition matrices into a plurality of sections;
independently apply, as a first scan, the scan technique to each of the plurality of sections to create a series of full products;
apply, as a second scan, the scan technique to the series of the full products of the first scan of each of the plurality of sections to create partial product scan results; and
distribute the partial product scan results from the second scan of each of the plurality of sections.
11. The non-transitory computer-readable medium of claim 10 , where the one or more instructions to output the output array include:
one or more instructions that, when executed by the one or more processors, cause the one or more processors to output data corresponding to a decoded version of the encoded data represented by the input array.
12. The non-transitory computer-readable medium of claim 8 , where the one or more instructions to calculate the products of the cumulative products of the series of transition matrices and the initialization vector include:
one or more instructions that, when executed by the one or more processors, cause the one or more processors to calculate the series of transition matrices from the input array.
13. The non-transitory computer-readable medium of claim 12 , where calculating the series of transition matrices and calculating the products of the cumulative products of the series of transition matrices and the initialization vector, are simultaneously performed for an alpha parameter of a Maximum A Posteriori Probability (MAP) decoder and a beta parameter of the MAP decoder.
14. The non-transitory computer-readable medium of claim 8 , where values in the series of transition matrices represent probabilities associated with state transitions in a Maximum A Posteriori Probability (MAP) decoder.
15. A device comprising:
one or more processors to:
calculate, in parallel, products of cumulative products of:
a series of transition matrices associated with an input array representing encoded data, and
an initialization vector;
calculate, based on the products of the cumulative products of the series of transition matrices and the initialization vector, an output array that corresponds to a decoded version of the encoded data; and
output the output array.
16. The device of claim 15 , where, when calculating the products of the cumulative products of the series of transition matrices and the initialization vector, the one or more processors are to:
use a scan technique to convert the series of transition matrices and the initialization vector into the products of the cumulative products of the series of transition matrices and the initialization vector.
17. The device of claim 16 , where, when calculating the products of the cumulative products of the series of transition matrices and the initialization vector, the one or more processors are to:
segment the series of transition matrices into a plurality of sections;
independently apply, as a first scan, the scan technique to each of the plurality of sections to calculate full products for the plurality of sections;
apply, as a second scan, the scan technique to a series of the full products of the first scan of each of the plurality of sections to calculate partial product scan results; and
distribute the partial product scan results from the second scan of each of the plurality of sections.
18. The device of claim 15 , where, when calculating the products of the cumulative products of the series of transition matrices and the initialization vector, the one or more processors are to:
calculate the series of transition matrices from the input array,
where calculating the series of transition matrices and calculating the products of the cumulative products of the series of transition matrices and the initialization vector, are simultaneously performed for an alpha parameter of a Maximum A Posteriori Probability (MAP) decoder and a beta parameter of the MAP decoder.
19. The device of claim 15 , where values in the series of transition matrices represent probabilities associated with state transitions in a Maximum A Posteriori Probability (MAP) decoder.
20. The device of claim 15 , where, when calculating the products of the cumulative products of the series of transition matrices and the initialization vector, the one or more processors are to:
perform matrix multiplication operations using a Max-Log-Map technique.