The standard algorithm for computing the soft-inverse of a finite-state machine [i.e., the soft-in/soft-out (SISO) module] is the forward-backward algorithm. These forward and backward recursions can be computed in pa...
详细信息
The standard algorithm for computing the soft-inverse of a finite-state machine [i.e., the soft-in/soft-out (SISO) module] is the forward-backward algorithm. These forward and backward recursions can be computed in parallel, yielding an architecture with latency O(N), where N is the block size, We demonstrate that the standard SISO computation may be formulated using a combination of prefix and suffix operations, Based on well-known tree-structures for fast parallel prefix computations in the very large scale integration (VLSI) literature (e,g,, tree adders), we propose a tree-structured SISO that has latency O(log, N), The decrease in latency comes primarily at a cost of area with, in some cases, only a marginal increase in computation. We discuss how this structure could be used to design a very high throughput turbo decoder or, more generally, an:iterative detector. Various subwindowing and tiling schemes are also considered to further improve latency.
Given a black-and-white image, represented by an array of square-root n x square-root n binary-valued pixels, we wish to cover the black pixels with a minimal set of (possibly overlapping) maximal squares. It was rece...
详细信息
Given a black-and-white image, represented by an array of square-root n x square-root n binary-valued pixels, we wish to cover the black pixels with a minimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining a minimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for the minimal square cover problem, which for any desired computation time T in [log n, n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.
暂无评论