Statistical mechanics of low-density parity check error-correcting codes over Galois fields

A variation of low-density parity check (LDPC) error-correcting codes defined over Galois fields (GF(q)) is investigated using statistical physics. A code of this type is characterised by a sparse random parity check matrix composed of C non-zero elements per column. We examine the dependence of the code performance on the value of q, for finite and infinite C values, both in terms of the thermodynamical transition point and the practical decoding phase characterised by the existence of a unique (ferromagnetic) solution. We find different q-dependence in the cases of C = 2 and C ≥ 3; the analytical solutions are in agreement with simulation results, providing a quantitative measure to the improvement in performance obtained using non-binary alphabets.

Properties of sparse random matrices over finite fields

Typical properties of sparse random matrices over finite (Galois) fields are studied, in the limit of large matrices, using techniques from the physics of disordered systems. For the case of a finite field GF(q) with prime order q, we present results for the average kernel dimension, average dimension of the eigenvector spaces and the distribution of the eigenvalues. The number of matrices for a given distribution of entries is also calculated for the general case. The significance of these results to error-correcting codes and random graphs is also discussed.

Typical performance of low-density parity-check codes over general symmetric channels

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel noise models.

Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach

Using methods of statistical physics, we study the average number and kernel size of general sparse random matrices over GF(q), with a given connectivity profile, in the thermodynamical limit of large matrices. We introduce a mapping of GF(q) matrices onto spin systems using the representation of the cyclic group of order q as the q-th complex roots of unity. This representation facilitates the derivation of the average kernel size of random matrices using the replica approach, under the replica symmetric ansatz, resulting in saddle point equations for general connectivity distributions. Numerical solutions are then obtained for particular cases by population dynamics. Similar techniques also allow us to obtain an expression for the exact and average number of random matrices for any general connectivity profile. We present numerical results for particular distributions.

Typical performance of regular low-density parity-check codes over general symmetric channels

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. Relationship between the free energy in statistical-mechanics approach and the mutual information used in the information-theory literature is established within a general framework; Gallager and MacKay-Neal codes are studied as specific examples of LDPC codes. It is shown that basic properties of these codes known for particular channels, including their potential to saturate Shannon's bound, hold for general symmetric channels. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel models.

Using interior point algorithms for the solution of linear programs with special structural features

Linear Programming (LP) is a powerful decision making tool extensively used in various economic and engineering activities. In the early stages the success of LP was mainly due to the efficiency of the simplex method. After the appearance of Karmarkar's paper, the focus of most research was shifted to the field of interior point methods. The present work is concerned with investigating and efficiently implementing the latest techniques in this field taking sparsity into account. The performance of these implementations on different classes of LP problems is reported here. The preconditional conjugate gradient method is one of the most powerful tools for the solution of the least square problem, present in every iteration of all interior point methods. The effect of using different preconditioners on a range of problems with various condition numbers is presented. Decomposition algorithms has been one of the main fields of research in linear programming over the last few years. After reviewing the latest decomposition techniques, three promising methods were chosen the implemented. Sparsity is again a consideration and suggestions have been included to allow improvements when solving problems with these methods. Finally, experimental results on randomly generated data are reported and compared with an interior point method. The efficient implementation of the decomposition methods considered in this study requires the solution of quadratic subproblems. A review of recent work on algorithms for convex quadratic was performed. The most promising algorithms are discussed and implemented taking sparsity into account. The related performance of these algorithms on randomly generated separable and non-separable problems is also reported.

Statistical mechanics of broadcast channels using low-density parity-check codes

We investigate the use of Gallager's low-density parity-check (LDPC) codes in a degraded broadcast channel, one of the fundamental models in network information theory. Combining linear codes is a standard technique in practical network communication schemes and is known to provide better performance than simple time sharing methods when algebraic codes are used. The statistical physics based analysis shows that the practical performance of the suggested method, achieved by employing the belief propagation algorithm, is superior to that of LDPC based time sharing codes while the best performance, when received transmissions are optimally decoded, is bounded by the time sharing limit.

Optimization of chemical plant simulation using double collocation

A method has been constructed for the solution of a wide range of chemical plant simulation models including differential equations and optimization. Double orthogonal collocation on finite elements is applied to convert the model into an NLP problem that is solved either by the VF 13AD package based on successive quadratic programming, or by the GRG2 package, based on the generalized reduced gradient method. This approach is termed simultaneous optimization and solution strategy. The objective functional can contain integral terms. The state and control variables can have time delays. Equalities and inequalities containing state and control variables can be included into the model as well as algebraic equations and inequalities. The maximum number of independent variables is 2. Problems containing 3 independent variables can be transformed into problems having 2 independent variables using finite differencing. The maximum number of NLP variables and constraints is 1500. The method is also suitable for solving ordinary and partial differential equations. The state functions are approximated by a linear combination of Lagrange interpolation polynomials. The control function can either be approximated by a linear combination of Lagrange interpolation polynomials or by a piecewise constant function over finite elements. The number of internal collocation points can vary by finite elements. The residual error is evaluated at arbitrarily chosen equidistant grid-points, thus enabling the user to check the accuracy of the solution between collocation points, where the solution is exact. The solution functions can be tabulated. There is an option to use control vector parameterization to solve optimization problems containing initial value ordinary differential equations. When there are many differential equations or the upper integration limit should be selected optimally then this approach should be used. The portability of the package has been addressed converting the package from V AX FORTRAN 77 into IBM PC FORTRAN 77 and into SUN SPARC 2000 FORTRAN 77. Computer runs have shown that the method can reproduce optimization problems published in the literature. The GRG2 and the VF I 3AD packages, integrated into the optimization package, proved to be robust and reliable. The package contains an executive module, a module performing control vector parameterization and 2 nonlinear problem solver modules, GRG2 and VF I 3AD. There is a stand-alone module that converts the differential-algebraic optimization problem into a nonlinear programming problem.

Suppression and summation in contrast gain control for human vision

Over the last ten years our understanding of early spatial vision has improved enormously. The long-standing model of probability summation amongst multiple independent mechanisms with static output nonlinearities responsible for masking is obsolete. It has been replaced by a much more complex network of additive, suppressive, and facilitatory interactions and nonlinearities across eyes, area, spatial frequency, and orientation that extend well beyond the classical recep-tive field (CRF). A review of a substantial body of psychophysical work performed by ourselves (20 papers), and others, leads us to the following tentative account of the processing path for signal contrast. The first suppression stage is monocular, isotropic, non-adaptable, accelerates with RMS contrast, most potent for low spatial and high temporal frequencies, and extends slightly beyond the CRF. Second and third stages of suppression are difficult to disentangle but are possibly pre- and post-binocular summation, and involve components that are scale invariant, isotropic, anisotropic, chromatic, achromatic, adaptable, interocular, substantially larger than the CRF, and saturated by contrast. The monocular excitatory pathways begin with half-wave rectification, followed by a preliminary stage of half-binocular summation, a square-law transducer, full binocular summation, pooling over phase, cross-mechanism facilitatory interactions, additive noise, linear summation over area, and a slightly uncertain decision-maker. The purpose of each of these interactions is far from clear, but the system benefits from area and binocular summation of weak contrast signals as well as area and ocularity invariances above threshold (a herd of zebras doesn't change its contrast when it increases in number or when you close one eye). One of many remaining challenges is to determine the stage or stages of spatial tuning in the excitatory pathway.

Dielectric relaxation of polysiloxanes and kerr effect of p-phenylene vinylene oligomers

The dielectric relaxation behaviour of a series of cyclic and linear poly(dimethylsiloxanes) with overline nn in the range 28 to 99 has been studied, as a function of temperature (142.0K-157.5K) and frequency (12-105Hz). Activation energies for the -relaxation process, Davidson-Cole empirical distribution factors, , and mean-square dipole moments per repeat unit, < 2> , have been calculated. Differences in values of H_act reflected restricted dipolar rotation for the cyclic structures, compared to the linear structures, over the range of molecular weights studied. The dielectric relaxation behaviour of a series of linear oligomers of methyl phenyl siloxane, with n in the range 4 to 10, a series of linear fractions of poly(methyl phenyl siloxane), with overline n_n in the range 31 to 1370, and a cyclic oligomer of mehyl phenyl siloxane, with n = 10, has been studied as a function of temperature (155.5K-264.0K) and frequency (12-105Hz). Activation energies for the -relaxation process, Davidson-Cole and Cole-Cole empirical distribution factors, and , respectively, and mean-square dipole moments per repeat unit have been calculated. The reduced flexibility of short methyl phenyl siloxane chains, compared to dimethyl siloxane chains, was apparent from a comparison of dipole moment ratios. The dilectric relaxation behaviour of poly(methyl hydrogen siloxane) and poly(n-hexyl methyl siloxane) has been studied as a function of temperature and frequency. A polysiloxane liquid crystal has been synthesised and its dielectric relaxation behaviour has been studied, as a function of temperature and frequency, in the liquid crystalline phase and below T_g. Poly(p-phenylene vinylene) and related oligomers have been synthesised and characterised by a variety of experimental techniques. The Kerr effect of two oligomeric fractions, in solution in PPG 2025, has been measured. The electrical conductivities of the undoped and I_2-doped polymer and oligomers have been measured.

Spatially extensive summation of contrast-energy is revealed by contrast detection of micro-pattern textures

Vision must analyze the retinal image over both small and large areas to represent fine-scale spatial details and extensive textures. The long-range neuronal convergence that this implies might lead us to expect that contrast sensitivity should improve markedly with the contrast area of the image. But this is at odds with the orthodox view that contrast sensitivity is determined merely by probability summation over local independent detectors. To address this puzzle, I aimed to assess the summation of luminance contrast without the confounding influence of area-dependent internal noise. I measured contrast detection thresholds for novel Battenberg stimuli that had identical overall dimensions (to clamp the aggregation of noise) but were constructed from either dense or sparse arrays of micro-patterns. The results unveiled a three-stage visual hierarchy of contrast summation involving (i) spatial filtering, (ii) long-range summation of coherent textures, and (iii) pooling across orthogonal textures. Linear summation over local energy detectors was spatially extensive (as much as 16 cycles) at Stage 2, but the resulting model is also consistent with earlier classical results of contrast summation (J. G. Robson & N. Graham, 1981), where co-aggregation of internal noise has obscured these long-range interactions.

Photonic skin for pressure and strain sensing

In this paper, we report on the strain and pressure testing of highly flexible skins embedded with Bragg grating sensors recorded in either silica or polymer optical fibre. The photonic skins, with a size of 10cm x 10cm and thickness of 1mm, were fabricated by embedding the polymer fibre or silica fibre containing Bragg gratings in Sylgard 184 from Dow Corning. Pressure sensing was studied using a cylindrical metal post placed on an array of points across the skin. The polymer fibre grating exhibits approximately 10 times the pressure sensitivity of the silica fibre and responds to the post even when it is placed a few centimetres away from the sensing fibre. Although the intrinsic strain sensitivities of gratings in the two fibre types are very similar, when embedded in the skin the polymer grating displayed a strain sensitivity approximately 45 times greater than the silica device, which also suffered from considerable hysteresis. The polymer grating displayed a near linear response over wavelength shifts of 9nm for 1% strain. The difference in behaviour we attribute to the much greater Young's modulus of the silica fibre (70 GPa) compared to the polymer fibre (3 GPa).

Highly sensitive liquid level monitoring system utilizing polymer fiber Bragg gratings

A novel and highly sensitive liquid level sensor based on a polymer optical fiber Bragg grating (POFBG) is experimentally demonstrated. Two different configurations are studied and both configurations show the potential to interrogate liquid level by measuring the strain induced in a POFBG embedded in a silicone rubber diaphragm, which deforms due to hydrostatic pressure variations. The sensor exhibits a highly linear response over the sensing range and a good repeatability. For comparison, a similar sensor using a FBG inscribed in silica fiber is fabricated, which displays a sensitivity that is a factor of 5 smaller than the POFBG. The temperature sensitivity is studied and a novel multi-sensor arrangement proposed which has the potential to provide level readings independent of temperature and the liquid density.

Fiber-optic liquid level monitoring system using microstructured polymer fiber Bragg grating array sensors:performance analysis

A highly sensitive liquid level monitoring system based on microstructured polymer optical fiber Bragg grating (mPOFBG) array sensors is reported for the first time. The configuration is based on five mPOFBGs inscribed in the same fiber in the 850 nm spectral region, showing the potential to interrogate liquid level by measuring the strain induced in each mPOFBG embedded in a silicone rubber (SR) diaphragm, which deforms due to hydrostatic pressure variations. The sensor exhibits a highly linear response over the sensing range, a good repeatability, and a high resolution. The sensitivity of the sensor is found to be 98 pm/cm of water, enhanced by more than a factor of 9 when compared to an equivalent sensor based on a silica fiber around 1550 nm. The temperature sensitivity is studied and a multi-sensor arrangement proposed, which has the potential to provide level readings independent of temperature and the liquid density.

Finite-connectivity spin-glass phase diagrams and low-density parity check codes

We obtain phase diagrams of regular and irregular finite-connectivity spin glasses. Contact is first established between properties of the phase diagram and the performance of low-density parity check (LDPC) codes within the replica symmetric (RS) ansatz. We then study the location of the dynamical and critical transition points of these systems within the one step replica symmetry breaking theory (RSB), extending similar calculations that have been performed in the past for the Bethe spin-glass problem. We observe that the location of the dynamical transition line does change within the RSB theory, in comparison with the results obtained in the RS case. For LDPC decoding of messages transmitted over the binary erasure channel we find, at zero temperature and rate R=14, an RS critical transition point at pc 0.67 while the critical RSB transition point is located at pc 0.7450±0.0050, to be compared with the corresponding Shannon bound 1-R. For the binary symmetric channel we show that the low temperature reentrant behavior of the dynamical transition line, observed within the RS ansatz, changes its location when the RSB ansatz is employed; the dynamical transition point occurs at higher values of the channel noise. Possible practical implications to improve the performance of the state-of-the-art error correcting codes are discussed. © 2006 The American Physical Society.