An elementary combinatorial Tanner graph construction for a family of near-regular low density parity check (LDPC) codes achieving high girth is presented. These codes are near regular in the sense that the degree of a left/right vertex is allowed to differ by at most one from the average. The construction yields in quadratic time complexity an asymptotic code family with provable lower bounds on the rate and the girth for a given choice of block length and average degree. The construction gives flexibility in the choice of design parameters of the code like rate, girth and average degree. Performance simulations of iterative decoding algorithm for the AWGN channel on codes designed using the method demonstrate that these codes perform better than regular PEG codes and MacKay codes of similar length for all values of Signal to noise ratio.

Two decision problems related to the computation f stopping sets in Tanner graphs are shown to be NP-complete. It follows as a consequence that there exists no polynomial time algorithm for computing the stopping distance of a Tanner graph unless P = NP.

Summary form only given. This paper proposes a new technique for tracking context to be used in a statistical code compression scheme for XML documents. Based on recursive finite state machines, the techniques employs an arithmetic coding scheme. The tradeoffs between space and compression ratio is studied by observing the effects of either using or ignoring root to leaf contexts for textual content in the associated tree structures. The scheme is syntax aware and the compressor and decompressor can be generated automatically from the document type definition (DTD) without interactive inputs from the user. A comparison of the path sensitive and path agnostic schemes for storing context for PCDATA was performed. Experimental results show that path sensitive schemes are less effective in the fixed memory model

A linear time approximate maximum likelihood decoding algorithm on tail-biting trellises is presented, that requires exactly two rounds on the trellis. This is an adaptation of an algorithm proposed earlier with the advantage that it reduces the time complexity from O(m log m) to O(m) where m is the number of nodes in the tail-biting trellis. A necessary condition for the output of the algorithm to differ from the output of the ideal ML decoder is deduced and simulation results on an AWGN channel using tail-biting trellises for two rate 1/2 convolutional codes with memory 4 and 6 respectively, are reported

Summary form only given. We propose a general purpose code compression scheme for embedded systems, based on the instruction set architecture and report results on the Intel StrongARM, a low-cost, low-power RISC architecture and TI TMS320C62x, a widely used VLIW architecture. Fast decompression techniques are explored to improve the decompression overhead of the compression scheme. Compression ratios ranging from 68% to 75% were obtained for TMS320C62x and 69% to 78% for the StrongARM processor. The basic idea of the compression scheme is to divide the instructions into different logical classes and to build multiple dictionaries for them. The size and the number of multiple dictionaries are fixed for a given processor and are determined by the partitioning algorithm which works over the instruction set architecture supplied as input. Frequently occurring unique instruction segments are inserted into the dictionaries and the instructions are encoded as pointers to the respective entries. An opcode, which helps in fast decompression, is attached to an instruction segment to identify its logical class and the dictionary to be accessed.

We propose two approximate algorithms for MAP decoding on tail-biting trellises. The algorithms work on a subset of nodes of the tail-biting trellis, judiciously selected. We report the results of simulations on an AWGN channel using the approximate algorithms on tail-biting trellises for the (24,12) extended Golay code and a rate 1/2 convolutional code with memory 6

An algorithm for exact maximum likelihood decoding on tail-biting trellises is analyzed and shows that under certain conditions exact maximum likelihood decoding has time complexity O(S/sub t/ log(S/sub t/)) and where S/sub t/ is the total number of states of the tail-biting trellis.

Summary form only given. A scheme for code compression that has a fast decompression algorithm, which can be implemented using simple hardware, is proposed. The effectiveness of the scheme on the TMS320C62x architecture that includes the overheads of a line address table (LAT) is evaluated and obtained compression rates ranging from 70% to 80%. Two schemes for decompression are proposed. The basic idea underlying the scheme is a simple clustering algorithm that partially maps a block of instructions into a set of clusters. The clustering algorithm is a greedy algorithm based on the frequency of occurrence of various instructions.

We propose a scheme for the compression of tree structured intermediate code consisting of a sequence of trees specified by a regular tree grammar. The scheme is based on arithmetic coding, and the model that works in conjunction with the coder is automatically generated from the syntactical specification of the tree language. Experiments on data sets consisting of intermediate code trees yield compression ratios ranging from 2.5 to 8, for file sizes ranging from 167 bytes to 1 megabyte.

We propose a new technique for constructing code-generator generators, which combines the advantages of the Graham-Glanville parsing technique and the bottom-up tree parsing approach. Machine descriptions are similar to Yacc specifications. The construction effectively generates a pushdown automaton as the matching device. This device is able to handle ambigious grammars, and can be used to generate locally optimal code without the use of heuristics. Cost computations are performed at preprocessing time. The class of regular tree grammars augmented with costs that can be handled by our system properly includes those that can be handled by bottom-up systems based on finite-state tree parsing automata. Parsing time is linear in the size of the subject tree. We have tested the system on specifications for some systems and report table sizes.

A modification of the linear quadtree, the threaded linear hierarchical quadtree (TLHQT), is proposed for the computation of geometric properties of binary images. Since most of the algorithms used in connection with computation of geometric properties require frequent exploration of adjacencies, a structure that keeps permanently in memory some adjacency links is introduced. Some results obtained by using the TLHQT for labeling connected components and for evaluating the perimeter and Euler's number in a quadtree environment are presented. The performance of the TLHQT is discussed.>

An algorithm to label the connected components of a binary picture is presented using a hierarchical version of the linear quadtree.2 This algorithm, which starts from the lowest level of the hierarchy, is shown to be computationally faster than the one using the topmost level as the starting point. The computational complexity of the algorithm appears comparable to that of existing methods due to Gargantini and Samet.4,5

Bose-Chadhuri-Hocquenghem (BCH) codes with symbols from an arbitrary finite integer ring are derived in terms of their generator polynomials. Tile derivation is based on the factorization ofx^{n}-1over the unit ring of an appropriate extension of the Finite integer ring. The construction is thus shown to be similar to that for BCH codes over finite fields.