A recent-result session will take place in the evening of
Monday, June 26. Authors interested in submitting
a contribution should contact

R. Michael Tanner
Computer Science
Applied Sciences #117
UC Santa Cruz
1156 High Street
Santa Cruz, CA 95064 (USA)

Ph:  +1 831 4592307
Fax: +1 831 4594829

e-mail: tanner@cse.ucsc.edu

Codes/Graphs

Title: A [155,64,20] Sparse Graph Code
Author: R. Michael Tanner, Professor of Computer Science Affiliation: University of California, Santa Cruz
Email: tanner@cse.ucsc.edu
Abstract:
A quasi-cyclic low-density parity-check code and graph with an algebraic definition is presented. It consists of 5 circles of 31 bit nodes and 3 circles of 31 parity nodes in which each bit is checked by 3 parities and each parity checks 5 bits. The code constraint graph has a minimum cycle length of 8 and a diameter of 6, which are optimal for a graph with these node degrees. Despite the sparseness, the true minimum distance of the code as determined by MAGMA is 20, which compares favorably with the [155,64,28] best code known. The quality of the code/graph makes it an interesting testbed for comparing the performance of various graph-message algorithms.

Title: Design of Good LDPC Codes Using Girth Distribution
Authors: Yongyi Mao and Amir H. Banihashemi (presenter) Affiliation: Dept. of Systems and Computer Engineering, Carleton University, Ottawa, Ontario, Canada
Email: ahashemi@sce.carleton.ca
Abstract:
An efficient method for the design of good LDPC codes given the block length, the rate, and the degree sequence is presented. The method is based on the Tanner graph representation of the code, and is particularly useful for short and intermediate block lengths (a few thousand bits or shorter). For such block lengths, a randomly selected code will most probably contain quite a few cycles which are short with respect to the number of iterations required for decoding. For these cases, our simulation results show that the performance of the codes does have a large variation. It also appears very difficult to find a good code from the ensemble merely based on trial and error. To overcome this, we define a property of the graph, called ``girth distribution," and use that as a selection criterion. Girth distribution g(l), l=4,6,8,...,lm, of a Tanner graph is defined as the fraction of the symbol nodes with girth l, where girth at node u is defined as the length of the shortest cycle that passes through u. It is observed that girth distribution is closely related to the performance of iterative decoding algorithms and can be efficiently computed, given the graph. Using the mean of the girth distribution, we design good LDPC codes for short and intermediate block lengths. Simulation results over AWGN channel show that codes selected by this criterion perform very well, most probably much better than an arbitrarily selected code from the ensemble.

Title: Maximum Likelihood Decoding as a Shortest Hyperpath Search on Hypertrellises
Author: Wai Ho MOW Affiliation: Hong Kong University of Science & Technology
Email: eewhmow@ust.hk
Abstract:
A hypertrellis model for codes is proposed as a weighted hypergraph generalization of the well-known trellis model. The time axis of a trellis has been extended to the so-called time topology, which may take the form of any factor hypergraph, the hypergraph equivalent of a factor graph. In this presentation, the maximum likelihood decoding (MLD) problem will be formulated as a shortest hyperpath search on decoding hypertrellises. This generalizes the well-known fact that MLD can be formulated as a shortest path search on decoding trellises. For hypertrellises with an acyclic time topology, the MLD problem can be solved by using a nonserial dynamic programming approach. The resultant one-way algorithm (OWA) generalizes the celebrated Viterbi algorithm (VA) from trellises to hypertrellises. Efficient management of hyperpath history for the OWA similar to that for the VA will also be presented. In addition, to characterize the complexity of a hypertrellis representation, the node complexity profile and the hyperedge complexity profile are introduced. These complexity profiles provide new useful criteria for comparing the decoding complexity associated with different hypertrellis representations of the same code.

Title: More Possibilities for Error-Correcting Codes
Authors: M. C. Rodríguez-Palánquex and L. J. García Villalba Affiliation: Universidad Complutense of Madrid (U.C.M.), Spain
Email: javiergv@sip.ucm.es
Abstract:
A new class of curves, the so-called Quasi-Hermitian curves, on Fq (with q = 2 ^ j) are presented. These curves are given by the affine equations y ^ a + B1 y + B2 x ^ (a+b) = 0 where a, b in Z, a >= 2, b >-a and B1, B2 in Fq - {0}. An algorithm which enables the exact minimum distance for the corresponding Goppa codes to be determined is also presented. This work leads to the possibility of constructing new version of such codes.

Shannon Theory/Source Coding/Data Compression

Title: A Variation of Lempel-Ziv String Matching Data Compression Method without Match Length Encoding
Author: Mitsuharu Arimura Affiliation: University of Electro-Communications
Email: arimura@is.uec.ac.jp
Abstract:
Since the Lempel-Ziv string matching data compression method, many variations have been proposed. One of the purposes of the variations is reducing the codeword length to describe the match length. Although many efforts have been made, all variations of the LZ77 method encode match length informations. We propose a new variation of Lempel-Ziv string matching data compression method. Our method parses string in the similar manner to the LZ77 algorithm, while, owing the modification of the parsing procedure, there is no need to encode the match length. We show that we can actually construct such a coding procedure and present the coding theorem.

Title: On Generalizations of the AEP: Densities or Balls?
Author: Ioannis Kontoyiannis and Amir Dembo Department of Statistics, Departments of Math. and of Statistics,Purdue University Stanford University
Email: yiannis@stat.purdue.edu, amir@stat.Stanford.EDU
Abstract:
For a finite-valued stationary ergodic source $\{X_n\}$, the Asymptotic Equipartition Property (AEP) states that $(-1/n)\log P_n(X_1^n)$ converges to the entropy rate $H$ of $\{X_n\}$, as $n\to\infty$ ($P_n$ denotes the distribution of $X_1^n=(X_1,X_2,\ldots,X_n)$). The generalized AEP for sources with general alphabets states that, if $\{Q_n\}$ are ``nice'' measures such that $P_n$ has density $f_n$ with respect to $Q_n$, then $(1/n)\log f_n(X_1^n)$ converges to the relative entropy rate $D=\lim_n (1/n)D(P_n\|Q_n)$. In the context of lossy data compression, another generalization of the AEP has been given: For ``nice'' measures $\{Q_n\}$, $(-1/n)\log Q_n(B(X_1^n,D))\to R(P,Q,D)$, where $B(X_1^n,D)$ denote ``distortion-balls'' of radius $D$, and $R(P,Q,D)$ is a constant rate function. We establish a connection between these two by looking at the limit of the distortion level $D\downarrow 0$. Under certain conditions, we prove that the limits $n\to \infty$ and $D\to 0$ can be interchanged, and in fact can be taken simultaneously, in any fashion.

Title: Exact prediction in Bernoulli sources with short memory
Authors: Peter Harremoes and Flemming Topsoe Affiliation: Herlev Amtsgymnasium, University of Copenhagen Denmark, Denmark
Email: topsoe@math.ku.dk
Abstract:
Normally optimal predictors can only be determined numerically, but in certain cases it is possible to find the optimal predictor exactly. The study of exact predictors leads to knowledge of the structure of the predictors in general. The predictor for a Bernoulli source depends both on the size of the alphabet and the memory. The exact optimal predictor will be determined for small memory sizes for an alphabet with 2 letters, and some indication of the dependency on the alphabet size will be given. The main technical problem turns out to be to establish a new type of inequalities between the entropy of a distribution and its index of coincidence (sum of squares of point probabilities). To do this one has to determine the strange shape of the range of the mapping which sends a probability distribution into the vector consisting of its index and its entropy.

Title: An algorithm leading to the best coding scheme for certain models defined by trees.
Authors: Flemming Topsoe and Peter Harremoes Affiliation: University of Copenhagen, Herlev Amtsgymnasium,Denmark Denmark
Email: topsoe@math.ku.dk
Abstract:
The overall goal of research is to determine the best predictor (in the sense of minimax redundancy) - or, equivalently, the best coding scheme - in a model which consists of all probability distributions defined on a set which is provided by a fixed partial ordering, considering only distributions which are consistent with the ordering (P(a)<=P(b) if a<=b). This problem was solved by Ryabko in the case of a total (linear) order. A tree defines a partial order i.e. nodes on a branch closer to the root come before nodes further away from the root. We present a solution for rooted trees T = T(a,b,...,x) with "uniform branching" given by the "branching numbers" a,b,...,x (i.e. a branches emerge from the root of the tree, b branches emerge from each of the a nodes thus defined etc.). The problem is relatively easy to solve if the optimal predictor assigns different probabilities to all nodes on the same branch. The algorithm developed depends on a certain identity and singles out exactly which nodes have equal probabilities for the optimal predictor.

Cryptography

Title: On the Possible Choices of Nonlinear Filters of m-Sequences
Authors: L. J. García Villalba and M. C. Rodríguez-Palánquex Affiliation: Universidad Complutense of Madrid (U.C.M.), Spain
Email: javiergv@sip.ucm.es
Abstract:
Most common sequence generators in stream cipher systems are based on a combination of LFSRs and nonlinear functions. Depending on whether the keystream involves one or more than one LFSR, the sequence generators are commonly classified into filter generators and combination generators. In both cases the linear complexity is a measure of the suitability of a keystream for its cryptographic application. In fact, the linear complexity of sequences obtained from a nonlinear combination of LFSR-sequences is mostly predictable. On the other hand, the linear complexity of the filter generators depends exclusively on the particular form of the filter and the LFSR characteristic polynomial. Generally speaking, there is no systematic method to predict the resulting complexity. In this work it is presented the possible classes of nonlinear filters with different cryptographic properties of period and linear complexity. Emphasis is on the cosets associated with a nonlinear filter since they determine the way of these classes.

Codes and Communication Systems

Title: Generalized Principal Ratio Combining for Space-Time Codes in Slowly Fading Channels
Authors: Young-Ju Kim and Hwang Soo Lee Affiliation: Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST)
Email: yjkim@spl.kaist.ac.kr
Abstract:
We present a generalized version of principal ratio combining (PRC) [1], which is a near-optimum detection scheme for space-time codes in slowly flat fading environments. In PRC, the performance penalty increases as the number of receive antennas increases. In the proposed scheme, receive antennas are optimally divided into K groups, and the PRC detection method is applied to each group. This shows a flexible tradeoff between performance and decoding complexity by choosing the appropriate K. When K > 1 , the problem becomes how to determine the number of elements in each group. The path gains do not have to be independent, but they are assumed as independent samples of complex Gaussian random variables. The grouping rules are as follows: i) If m/K is an integer: The number of elements in each group is m/K. ii) If m/K is not an integer: The nearest integer of m/K is selected for the number of elements in each group and the surplus (or shortage) is allotted to each group as fairly as possible. In the simulation, a four-state QPSK space-time trellis code is employed. In this example, the performance loss grows larger as the SNR increases. Performance degradation gets even more severe as the number of receive antennas increases. Increasing K ( >1 ) using the above rules can mitigate the performance loss at the expense of increased decoding complexity. The performance results show that the rules outlined before are justified. Generalized suboptimum decoding of space-time codes includes ML and PRC. Knowing the flexible tradeoff between performance and decoding complexity will aid engineers to implement the most efficient space-time decoder.

Title: Jack Wolf's Analog Codes for Peak-to-Average Ratio Reduction
Author: Werner Henkel Affiliation: Telecommunications Research Center Vienna Maderstr. 1, A-1040 Vienna, Austria
Email: Werner.Henkel@ieee.org
Abstract:
Multi-tone modulation (DMT, Discrete Multitone, OFDM, Orthogonal Frequency Division Multiplex) has the disadvantage of a quite high peak-to-average ratio. Clipping of the high amplitudes caused by amplifiers and D/A-(A/D)-converters leads to additional noise. We show that, in principal, so-called Analog Codes (Reed-Solomon Codes over complex numbers) can be used for eliminating this noise. RS Codes can be defined as the samples of a polynomial with limited degree of $K-1$ where $K$ is the number of information symbols. This allows to correct spiky clipping disturbances by polynomial interpolation. In the decoding of RS codes, other possibilities like the extension of the syndrome using a shift register with coefficients given by the error-locator polynomial are also well known. In the case of clipping, the receiver could easily detect the error position by simple thresholding leading to the special case of erasure decoding. We found that, of course, the performance of the method is dependent on the succession of the non-linearity and the filtering involved. Two extreme situations have been considered: having all filtering after the clipping and vice versa. These scenarios halfways represent the DMT (wireline) and OFDM (wireless) applications, respectively. A filtering after the non-linearity can be almost completely equalized by the time- and DFT-domain equalization in the multi-tone receiver, and thus, has no influence on the performance. Filtering preceding the non-linearity, however, leads to more and higher peaks to be clipped (over-shooting). Thereby, the error/erasure-correcting capability of a RS code is easily exceeded and clipping-noise reduction gains are reduced drastically. Anyway, the out-of-band noise caused by clipping will not make the method attractive for OFDM applications. In the case of DMT, it may be a worthwhile alternative, if the out-of-band power and especially the filling of notches in the spectrum at amateur-radio bands are not an issue. For further information, see, http://www.ftw.at/publication\_en.html. {FTW is part of the it plus program which is co-financed by the Austrian Federal Ministry of Science and Transport and the City of Vienna}

Title: On the Performance of Golay Complementary Pairs for the Base Station Acquisition in WCDMA
Authors: Jyoti Bali and Inhyok Cha R G Davenport Affiliation: Wireless Networks Group MC2 Technology Group, LLC Lucent Technologies Hemlock New Jersey, USA New York, USA
E-mail: jbali1@lucent.com
Abstract:
In order to communicate with a WCDMA base station, a mobile must first synchronize to the base station system clock. Since the Primary Synchronization Code (PSC) is sent as a burst sequence at the beginning of each time slot, it is desirable to select a code with low acyclic-correlation sidelobes. In the current 3GPP (Third Generation Partnership Project) standard, slot synchronization is accomplished with a 256-bit Hierarchical Golay Code (HGC) which does not have the above-mentioned desirable properties. The acyclic correlation of the HGC is multi-valued with a maximum correlation sidelobe of 64 compared with a lag zero correlation value of 256. Thus, in order to maintain a low probability of false synchronization, the decision threshold must be maintained within the 12 dB range established by this high peak to sidelobe ratio.
On the other hand, a Golay complementary pair is ideal because the acyclic correlation sidelobes of the two constituent sequences are complementary. When the autocorrelation functions of the constituent sequences are summed, the sidelobes cancel for all lags except lag zero, where the individual autocorrelation peaks sum to a value proportional to twice the length of the sequence. Thus, for a 256 bit sequence in the absence of noise, the synchronization decision threshold can be set anywhere within the 54 dB dynamic range (20*log [512]) of the correlator output.
Currently, the HGC is transmitted simultaneously on both the inphase and the Quadrature channels. It is a simple matter to substitute the Golay Complementary pair by transmitting one Golay sequence on the I channel and its complement on the Q channel. This requires the addition of a second sequence generator in the base station, but does not affect the basic architecture of the PSC transmission method. Similarly, the mobile will require the addition of a second correlator and summing device, but again the basic architecture is unaffected.
This paper discusses the properties of the Golay Complementary Sequence, provides a comparative analysis and simulation results of the existing HGC and the proposed Golay-pair codes, and describes the additional hardware required to implement the improved PSC technique.

Title: The coding-spreading trade-off for CDMA systems with frequency selective fading
Author: Ashok Mantravadi and Venugopal Veeravalli Affiliation: Cornell University
Email : ashok@ee.cornell.edu
Abstract:
In typical Code Division Multiple Access (CDMA) systems, the bandwidth of each user's information bearing signal is expanded through two different operations: coding and spreading. The trade-off problem consists of dividing the available bandwidth between these two operations in some optimal way, e.g., to maximize the spectral efficiency of the system. We consider the trade-off problem for wideband CDMA systems, where the receiver can resolve multiple shifted copies of each user's signal. The receiver is assumed to have perfect channel state information, and is assumed to consist of a linear detector followed by single-user autonomous decoders. An interesting aspect of the trade-off problem in this setting is the inter-symbol interference caused by mutipath propagation. Analytical insights can be obtained in the asymptotic regime of infinite bandwidth, where the processing gain, the number of users and the number of resolvable paths approach infinity. The results obtained analytically are compared with finite-system simulations. Specifically, spectral efficiencies achievable using the conventional matched-filter and linear minimum mean-squared error (MMSE) detectors are studied.