18739074
Product accumulate codes: a class of codes with near-capacity performance and low decoding complexity
We propose a novel class of provably good codes which are a serial concatenation of a single-parity-check (SPC)-based product code, an interleaver, and a rate-1 recursive convolutional code. The proposed codes, termed product accumulate (PA) codes, are linear time encodable and linear time decodable. We show that the product code by itself does not have a positive threshold, but a PA code can provide arbitrarily low bit-error rate (BER) under both maximum-likelihood (ML) decoding and iterative decoding. Two message-passing decoding algorithms are proposed and it is shown that a particular update schedule for these message-passing algorithms is equivalent to conventional turbo decoding of the serial concatenated code, but with significantly lower complexity. Tight upper bounds on the ML performance using Divsalar's (1999) simple bound and thresholds under density evolution (DE) show that these codes are capable of performance within a few tenths of a decibel away from the Shannon limit. Simulation results confirm these claims and show that these codes provide performance similar to turbo codes but with significantly less decoding complexity and with a lower error floor. Hence, we propose PA codes as a class of prospective codes with good performance, low decoding complexity, regular structure, and flexible rate adaptivity for all rates above 1/2.
5813822
A Class of High-rate, Low-complexity, Well- structured LDPC Codes from Combinatorial Designs and their Applications on ISI Channels
We present a systematic construction of a class of highrate, well-structured low density parity check (LDPC) codes based on combinatorial designs. We show that the proposed -design results in a class of -regular LDPC codes, which are systematic, quasicyclic, free of length-4 and length-6 cycles, linear-time encodable and decodable, and which have high code rates of . Analysis from the maximum likelihood perspective shows that the distance spectrum of the proposed LDPC codes are better than that of the Gallager ensemble codes for the same code length and rate. The proposed codes are then applied to several inter-symbol interference channels, where 2 high code rates and 3 block sizes from short to mediumn are evaluated. For best performance gain, the i.i.d. capacity is computed to choose the best precoder and iterative decoding and equalization is performed The proposed LDPC codes demonstrate performance that is slightly (but noticeably) better than an average random LDPC code of column weight 3. Unlike random codes, well-structured LDPC codes can lend themselves to a very low-complexity implementation for highspeed applications.
2641936
Slepian-Wolf coding for nonuniform sources using turbo codes
The recently proposed turbo-binning scheme is shown to be both efficient and optimal for uniform source Slepian-Wolf coding problem (Z. Tu et al., 2003). This paper studies the case when sources are i.i.d. but nonuniformly distributed. It is firstly shown that any algebraic binning scheme based on linear codes is optimal for nonuniform sources only asymptotically. Next two modifications are proposed to improve the performance of the turbo-binning scheme for nonuniform sources. The first is to carefully design the constituent encoder structures to maximally match the turbo code to the nonuniform source distribution, and the second is to use variable-length syndrome sequences to index the bins. Simulations show that the combination of both strategies can lead to an improvement of as much as 0.22 bit/symbol in overall compression rate for highly nonuniform sources.
38727821
Image classification based on a multiresolution two dimensional hidden Markov model
This paper presents an image classification algorithm based upon a two dimensional multiresolution hidden Markov model (MHMM). This model represents an image by feature vectors in several resolutions and considers the feature vectors statistically dependent through an underlying state process assumed to be a multiscale Markov mesh. To estimate the model by the maximum likelihood criterion, approximations are made successively based on the EM algorithm to reach feasible computation. To classify an image, the algorithm attempts to find the optimal set of states with the maximum a posteriori probability. The states are then mapped into classes. The multiresolution model enables multiscale context information to be incorporated into classification. Suboptimal algorithms based on the model provide progressive classification which greatly speeds up classification based on single resolution HMMs.
10602845
Maximizing Throughput for Optical Burst Switching Networks
A key problem in optical burst switching (OBS) is to schedule as many bursts as possible on wavelength channels so that the throughput is maximized and the burst loss is minimized. In this paper, we use competitive analysis to analyze the worst-case performance of a large set of scheduling algorithms, called best-effort online scheduling algorithms, for OBS networks, and establish a number of interesting upper and lower bounds on the performance of such algorithms. A surprising discovery is that the worst-case performance of any best-effort online scheduling algorithm is primarily determined by the maximum to minimum burst length ratio, followed by the range of offset time. Furthermore, if all bursts have the same burst length and offset time, all best-effort online scheduling algorithms generate the same optimal solution, regardless how different they may look like. Our analysis can also be extended to some nonbest-effort online scheduling algorithms, such as the well-known Horizon algorithm, and establish similar bounds. Based on the analytic results, we give guidelines for several widely discussed OBS problems, including burst assembly, offset time setting and scheduling algorithm design, and propose a new channel reservation protocol called VFO to improve the worst-case performance. Our simulation shows that it is quite often for an online scheduling algorithm to exhibit its (near) worst-case performance. Thus improving the worst-case performance is essential. Our simulation also suggests that VFO reduces the average burst loss rate by as much as 35%
62613535
OACerts: Oblivious Attribute Certificates
We propose oblivious attribute certificates (OACerts), an attribute certificate scheme in which a certificate holder can select which attributes to use and how to use them. In particular, a user can use attribute values stored in an OACert obliviously, i.e., the user obtains a service if and only if the attribute values satisfy the policy of the service provider, yet the service provider learns nothing about these attribute values. This way, the service provider's access control policy is enforced in an oblivious fashion. To enable the oblivious access control using OACerts, we propose a new cryptographic primitive called oblivious commitment-based envelope (OCBE). In an OCBE scheme, Bob has an attribute value committed to Alice and Alice runs a protocol with Bob to send an envelope (encrypted message) to Bob such that: 1) Bob can open the envelope if and only if his committed attribute value satisfies a predicate chosen by Alice and 2) Alice learns nothing about Bob's attribute value. We develop provably secure and efficient OCBE protocols for the Pedersen commitment scheme and comparison predicates as well as logical combinations of them
6271246
Mining Optimal Class Association Rule Set
We define an optimal class association rule set to be the minimum rule set with the same prediction power of the complete class association rule set. Using this rule set instead of the complete class association rule set we can avoid redundant computation that would otherwise be required for mining predictive association rules and hence improve the efficiency of the mining process significantly. We present an efficient algorithm for mining the optimal class association rule set using an upward closure property of pruning weak rules before they are actually generated. We have implemented the algorithm and our experimental results show that our algorithm generates the optimal class association rule set, whose size is smaller than 1/17 of the complete class association rule set on average, in significantly less time than generating the complete class association rule set. Our proposed criterion has been shown very effective for pruning weak rules in dense databases.
2012673
Mining the smallest association rule set for predictions
Mining transaction databases for association rules usually generates a large number of rules, most of which are unnecessary when used for subsequent prediction. In this paper we define a rule set for a given transaction database that is much smaller than the association rule set but makes the same predictions as the association rule set by the confidence priority. We call this subset the informative rule set. The informative rule set is not constrained to particular target items; and it is smaller than the non-redundant association rule set. We present an algorithm to directly generate the informative rule set, i.e., without generating all frequent itemsets first, and that accesses the database less often than other unconstrained direct methods. We show experimentally that the informative rule set is much smaller than both the association rule set and the non-redundant association rule set, and that it can be generated more efficiently.