OpenRaiser/Intern-Atlas huggingface dataset:
On Achievable Rates and Complexity of LDPC Codes for Parallel Channels with Application to Puncturing
Venue: arXiv cs.IT 2005
Year: 2005

This paper considers the achievable rates and decoding complexity of low-density parity-check (LDPC) codes over statistically independent parallel channels. The paper starts with the derivation of bounds on the conditional entropy of the transmitted codeword given the received sequence at the output of the parallel channels; the component channels are considered to be memoryless, binary-input, and output-symmetric (MBIOS). These results serve for the derivation of an upper bound on the achievable rates of ensembles of LDPC codes under optimal maximum-likelihood (ML) decoding when their transmission takes place over parallel MBIOS channels. The paper relies on the latter bound for obtaining upper bounds on the achievable rates of ensembles of randomly and intentionally punctured LDPC codes over MBIOS channels. The paper also provides a lower bound on the decoding complexity (per iteration) of ensembles of LDPC codes under message-passing iterative decoding over parallel MBIOS channels; the bound is given in terms of the gap between the rate of these codes for which reliable communication is achievable and the channel capacity. The paper presents a diagram which shows interconnections between the theorems introduced in this paper and some other previously reported results. The setting which serves for the derivation of the bounds on the achievable rates and decoding complexity is general, and the bounds can be applied to other scenarios which can be treated as different forms of communication over parallel channels.
On the Asymptotic Performance of Iterative Decoders for Product Codes
Venue: arXiv cs.IT 2005
Year: 2005

We consider hard-decision iterative decoders for product codes over the erasure channel, which employ repeated rounds of decoding rows and columns alternatingly. We derive the exact asymptotic probability of decoding failure as a function of the error-correction capabilities of the row and column codes, the number of decoding rounds, and the channel erasure probability. We examine both the case of codes capable of correcting a constant amount of errors, and the case of codes capable of correcting a constant fraction of their length.
High-performance BWT-based Encoders
Venue: arXiv cs.DS 2005
Year: 2005

In 1994, Burrows and Wheeler developed a data compression algorithm which performs significantly better than Lempel-Ziv based algorithms. Since then, a lot of work has been done in order to improve their algorithm, which is based on a reversible transformation of the input string, called BWT (the Burrows-Wheeler transformation). In this paper, we propose a compression scheme based on BWT, MTF (move-to-front coding), and a version of the algorithms presented in [Dragos Trinca, ITCC-2004].
Translating the EAH Data Compression Algorithm into Automata Theory
Venue: arXiv cs.DS 2005
Year: 2005

Adaptive codes have been introduced in [Dragos Trinca, cs.DS/0505007] as a new class of non-standard variable-length codes. These codes associate variable-length codewords to symbols being encoded depending on the previous symbols in the input data string. A new data compression algorithm, called EAH, has been introduced in [Dragos Trinca, cs.DS/0505061], where we have behaviorally shown that for a large class of input data strings, this algorithm substantially outperforms the well-known Lempel-Ziv universal data compression algorithm. In this paper, we translate the EAH encoder into automata theory.
Capacity of Ultra Wide Band Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2005
Year: 2005

Throughput capacity is a critical parameter for the design and evaluation of ad-hoc wireless networks. Consider n identical randomly located nodes, on a unit area, forming an ad-hoc wireless network. Assuming a fixed per node transmission capability of T bits per second at a fixed range, it has been shown that the uniform throughput capacity per node r(n) is Theta((T)/(sqrt{n log n})), a decreasing function of node density n. However an alternate communication model may also be considered, with each node constrained to a maximum transmit power P_0 and capable of utilizing W Hz of bandwidth. Under the limiting case W rightarrow infinity, such as in Ultra Wide Band (UWB) networks, the uniform throughput per node is O ((n log n)^{(alpha-1}/2}) (upper bound) and Omega((n^{(alpha-1)/2})/((log n)^{(alpha +1)/2})) (achievable lower bound). These bounds demonstrate that throughput increases with node density $n$, in contrast to previously published results. This is the result of the large bandwidth, and the assumed power and rate adaptation, which alleviate interference. Thus, the effect of physical layer properties on the capacity of ad hoc wireless networks is demonstrated. Further, the promise of UWB as a physical layer technology for ad-hoc networks is justified.
A Generalised Hadamard Transform
Venue: arXiv cs.IT 2005
Year: 2005

A Generalised Hadamard Transform for multi-phase or multilevel signals is introduced, which includes the Fourier, Generalised, Discrete Fourier, Walsh-Hadamard and Reverse Jacket Transforms. The jacket construction is formalised and shown to admit a tensor product decomposition. Primary matrices under this decomposition are identified. New examples of primary jacket matrices of orders 8 and 12 are presented.
An Improved Non-Termination Criterion for Binary Constraint Logic Programs
Venue: arXiv cs.PL 2005
Year: 2005

On one hand, termination analysis of logic programs is now a fairly established research topic within the logic programming community. On the other hand, non-termination analysis seems to remain a much less attractive subject. If we divide this line of research into two kinds of approaches: dynamic versus static analysis, this paper belongs to the latter. It proposes a criterion for detecting non-terminating atomic queries with respect to binary CLP clauses, which strictly generalizes our previous works on this subject. We give a generic operational definition and a logical form of this criterion. Then we show that the logical form is correct and complete with respect to the operational definition.
Enhancing the Alloy Analyzer with Patterns of Analysis
Venue: arXiv cs.SE 2005
Year: 2005

Formal techniques have been shown to be useful in the development of correct software. But the level of expertise required of practitioners of these techniques prohibits their widespread adoption. Formal techniques need to be tailored to the commercial software developer. Alloy is a lightweight specification language supported by the Alloy Analyzer (AA), a tool based on off-the-shelf SAT technology. The tool allows a user to check interactively whether given properties are consistent or valid with respect to a high-level specification, providing an environment in which the correctness of such a specification may be established. However, Alloy is not particularly suited to expressing program specifications and the feedback provided by AA can be misleading where the specification under analysis or the property being checked contains inconsistencies. In this paper, we address these two shortcomings. Firstly, we present a lightweight language called "Loy", tailored to the specification of object-oriented programs. An encoding of Loy into Alloy is provided so that AA can be used for automated analysis of Loy program specifications. Secondly, we present some "patterns of analysis" that guide a developer through the analysis of a Loy specification in order to establish its correctness before implementation.
New Sequence Sets with Zero-Correlation Zone
Venue: arXiv cs.IT 2005
Year: 2005

A method for constructing sets of sequences with zero-correlation zone (ZCZ sequences) and sequence sets with low cross correlation is proposed. The method is to use families of short sequences and complete orthogonal sequence sets to derive families of long sequences with desired correlation properties. It is a unification of works of Matsufuji and Torii \emph{et al.}, and there are more choices of parameters of sets for our method. In particular, ZCZ sequence sets generated by the method can achieve a related ZCZ bound. Furthermore, the proposed method can be utilized to derive new ZCZ sets with both longer ZCZ and larger set size from known ZCZ sets. These sequence sets are applicable in broadband satellite IP networks.
A Sorting Algorithm Based on Calculation
Venue: arXiv cs.DS 2005
Year: 2005

This article introduces an adaptive sorting algorithm that can relocate elements accurately by substituting their values into a function which we name it the guessing function. We focus on building this function which is the mapping relationship between record values and their corresponding sorted locations essentially. The time complexity of this algorithm O(n),when records distributed uniformly. Additionally, similar approach can be used in the searching algorithm.
A Closed-Form Solution for the Finite Length Constant Modulus Receiver
Venue: arXiv cs.GT 2005
Year: 2005

In this paper, a closed-form solution minimizing the Godard or Constant Modulus (CM) cost function under the practical conditions of finite SNR and finite equalizer length is derived. While previous work has been reported by Zeng et al., IEEE Trans. Information Theory. 1998, to establish the link between the constant modulus and Wiener receivers, we show that under the Gaussian approximation of intersymbol interference at the output of the equalizer, the CM finite-length receiver is equivalent to the nonblind MMSE equalizer up to a complex gain factor. Some simulation results are provided to support the Gaussian approximation assumption.
Mapping DEVS Models onto UML Models
Venue: arXiv cs.OH 2005
Year: 2005

Discrete event simulation specification (DEVS) is a formalism designed to describe both discrete state and continuous state systems. It is a powerful abstract mathematical notation. However, until recently it lacked proper graphical representation, which made computer simulation of DEVS models a challenging issue. Unified modeling language (UML) is a multipurpose graphical modeling language, a de-facto industrial modeling standard. There exist several commercial and open-source UML editors and code generators. Most of them can save UML models in XML-based XMI files ready for further automated processing. In this paper, we propose a mapping of DEVS models onto UML state and component diagrams. This mapping may lead to an eventual unification of the two modeling formalisms, combining the abstractness of DEVS and expressive power and ``computer friendliness'' of the UML.
Joint Equalization and Decoding for Nonlinear Two-Dimensional Intersymbol Interference Channels with Application to Optical Storage
Venue: arXiv cs.IT 2005
Year: 2005

An algorithm that performs joint equalization and decoding for nonlinear two-dimensional intersymbol interference channels is presented. The algorithm performs sum-product message-passing on a factor graph that represents the underlying system. The two-dimensional optical storage (TWODOS) technology is an example of a system with nonlinear two-dimensional intersymbol interference. Simulations for the nonlinear channel model of TWODOS show significant improvement in performance over uncoded performance. Noise tolerance thresholds for the algorithm for the TWODOS channel, computed using density evolution, are also presented and accurately predict the limiting performance of the algorithm as the codeword length increases.
Density Evolution for Asymmetric Memoryless Channels
Venue: arXiv cs.IT 2005
Year: 2005

Density evolution is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution (DE) has been widely and successfully applied to different channels, including binary erasure channels, binary symmetric channels, binary additive white Gaussian noise channels, etc. This paper generalizes density evolution for non-symmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g. z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation algorithm even when only symmetric channels are considered. Hence the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels.
Requirements for Digital Preservation Systems: A Bottom-Up Approach
Venue: arXiv cs.DL 2005
Year: 2005

The field of digital preservation is being defined by a set of standards developed top-down, starting with an abstract reference model (OAIS) and gradually adding more specific detail. Systems claiming conformance to these standards are entering production use. Work is underway to certify that systems conform to requirements derived from OAIS. We complement these requirements derived top-down by presenting an alternate, bottom-up view of the field. The fundamental goal of these systems is to ensure that the information they contain remains accessible for the long term. We develop a parallel set of requirements based on observations of how existing systems handle this task, and on an analysis of the threats to achieving the goal. On this basis we suggest disclosures that systems should provide as to how they satisfy their goals.
Haskell's overlooked object system
Venue: arXiv cs.PL 2005
Year: 2005

Haskell provides type-class-bounded and parametric polymorphism as opposed to subtype polymorphism of object-oriented languages such as Java and OCaml. It is a contentious question whether Haskell 98 without extensions, or with common extensions, or with new extensions can fully support conventional object-oriented programming with encapsulation, mutable state, inheritance, overriding, statically checked implicit and explicit subtyping, and so on. We systematically substantiate that Haskell 98, with some common extensions, supports all the conventional OO features plus more advanced ones, including first-class lexically scoped classes, implicitly polymorphic classes, flexible multiple inheritance, safe downcasts and safe co-variant arguments. Haskell indeed can support width and depth, structural and nominal subtyping. We address the particular challenge to preserve Haskell's type inference even for objects and object-operating functions. The OO features are introduced in Haskell as the OOHaskell library. OOHaskell lends itself as a sandbox for typed OO language design.
Friends for Free: Self-Organizing Artificial Social Networks for Trust and Cooperation
Venue: arXiv cs.MA 2005
Year: 2005

By harvesting friendship networks from e-mail contacts or instant message "buddy lists" Peer-to-Peer (P2P) applications can improve performance in low trust environments such as the Internet. However, natural social networks are not always suitable, reliable or available. We propose an algorithm (SLACER) that allows peer nodes to create and manage their own friendship networks. We evaluate performance using a canonical test application, requiring cooperation between peers for socially optimal outcomes. The Artificial Social Networks (ASN) produced are connected, cooperative and robust - possessing many of the disable properties of human friendship networks such as trust between friends (directly linked peers) and short paths linking everyone via a chain of friends. In addition to new application possibilities, SLACER could supply ASN to P2P applications that currently depend on human social networks thus transforming them into fully autonomous, self-managing systems.
Optimal Power Control for Multiuser CDMA Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we define the power region as the set of power allocations for K users such that everybody meets a minimum signal-to-interference ratio (SIR). The SIR is modeled in a multiuser CDMA system with fixed linear receiver and signature sequences. We show that the power region is convex in linear and logarithmic scale. It furthermore has a componentwise minimal element. Power constraints are included by the intersection with the set of all viable power adjustments. In this framework, we aim at minimizing the total expended power by minimizing a componentwise monotone functional. If the feasible power region is nonempty, the minimum is attained. Otherwise, as a solution to balance conflicting interests, we suggest the projection of the minimum point in the power region onto the set of viable power settings. Finally, with an appropriate utility function, the problem of minimizing the total expended power can be seen as finding the Nash bargaining solution, which sheds light on power assignment from a game theoretic point of view. Convexity and componentwise monotonicity are essential prerequisites for this result.
Capacity of Complexity-Constrained Noise-Free CDMA
Venue: arXiv cs.IT 2005
Year: 2005

An interference-limited noise-free CDMA downlink channel operating under a complexity constraint on the receiver is introduced. According to this paradigm, detected bits, obtained by performing hard decisions directly on the channel's matched filter output, must be the same as the transmitted binary inputs. This channel setting, allowing the use of the simplest receiver scheme, seems to be worthless, making reliable communication at any rate impossible. We prove, by adopting statistical mechanics notion, that in the large-system limit such a complexity-constrained CDMA channel gives rise to a non-trivial Shannon-theoretic capacity, rigorously analyzed and corroborated using finite-size channel simulations.
Club Formation by Rational Sharing : Content, Viability and Community Structure
Venue: arXiv cs.NI 2005
Year: 2005

A sharing community prospers when participation and contribution are both high. We suggest the two, while being related decisions every peer makes, should be given separate rational bases. Considered as such, a basic issue is the viability of club formation, which necessitates the modelling of two major sources of heterogeneity, namely, peers and shared content. This viability perspective clearly explains why rational peers contribute (or free-ride when they don't) and how their collective action determines viability as well as the size of the club formed. It also exposes another fundamental source of limitation to club formation apart from free-riding, in the community structure in terms of the relation between peers' interest (demand) and sharing (supply).
On Deciding Deep Holes of Reed-Solomon Codes
Venue: arXiv cs.IT 2005
Year: 2005

For generalized Reed-Solomon codes, it has been proved \cite{GuruswamiVa05} that the problem of determining if a received word is a deep hole is co-NP-complete. The reduction relies on the fact that the evaluation set of the code can be exponential in the length of the code -- a property that practical codes do not usually possess. In this paper, we first presented a much simpler proof of the same result. We then consider the problem for standard Reed-Solomon codes, i.e. the evaluation set consists of all the nonzero elements in the field. We reduce the problem of identifying deep holes to deciding whether an absolutely irreducible hypersurface over a finite field contains a rational point whose coordinates are pairwise distinct and nonzero. By applying Schmidt and Cafure-Matera estimation of rational points on algebraic varieties, we prove that the received vector $(f(α))_{α\in \F_q}$ for Reed-Solomon $[q,k]_q$, $k < q^{1/7 - ε}$, cannot be a deep hole, whenever $f(x)$ is a polynomial of degree $k+d$ for $1\leq d < q^{3/13 -ε}$.
Decomposing Solution Sets of Polynomial Systems: A New Parallel Monodromy Breakup Algorithm
Venue: arXiv cs.DC 2005
Year: 2005

We consider the numerical irreducible decomposition of a positive dimensional solution set of a polynomial system into irreducible factors. Path tracking techniques computing loops around singularities connect points on the same irreducible components. The computation of a linear trace for each factor certifies the decomposition. This factorization method exhibits a good practical performance on solution sets of relative high degrees. Using the same concepts of monodromy and linear trace, we present a new monodromy breakup algorithm. It shows a better performance than the old method which requires construction of permutations of witness points in order to break up the solution set. In contrast, the new algorithm assumes a finer approach allowing us to avoid tracking unnecessary homotopy paths. As we designed the serial algorithm keeping in mind distributed computing, an additional advantage is that its parallel version can be easily built. Synchronization issues resulted in a performance loss of the straightforward parallel version of the old algorithm. Our parallel implementation of the new approach bypasses these issues, therefore, exhibiting a better performance, especially on solution sets of larger degree.
Planar Earthmover is not in $L_1$
Venue: arXiv cs.CG 2005
Year: 2005

We show that any $L_1$ embedding of the transportation cost (a.k.a. Earthmover) metric on probability measures supported on the grid $\{0,1,...,n\}^2\subseteq \R^2$ incurs distortion $Ω(\sqrt{\log n})$. We also use Fourier analytic techniques to construct a simple $L_1$ embedding of this space which has distortion $O(\log n)$.
On the Capacity of Doubly Correlated MIMO Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we analyze the capacity of multiple-input multiple-output (MIMO) Rayleigh-fading channels in the presence of spatial fading correlation at both the transmitter and the receiver, assuming that the channel is unknown at the transmitter and perfectly known at the receiver. We first derive the determinant representation for the exact characteristic function of the capacity, which is then used to determine the trace representations for the mean, variance, skewness, kurtosis, and other higher-order statistics (HOS). These results allow us to exactly evaluate two relevant information-theoretic capacity measures--ergodic capacity and outage capacity--and the HOS of the capacity for such a MIMO channel. The analytical framework presented in the paper is valid for arbitrary numbers of antennas and generalizes the previously known results for independent and identically distributed or one-sided correlated MIMO channels to the case when fading correlation exists on both sides. We verify our analytical results by comparing them with Monte Carlo simulations for a correlation model based on realistic channel measurements as well as a classical exponential correlation model.