Generalized distributive law for ML decoding of STBCs

The Generalized Distributive Law (GDL) is a message passing algorithm which can efficiently solve a certain class of computational problems, and includes as special cases the Viterbi's algorithm, the BCJR algorithm, the Fast-Fourier Transform, Turbo and LDPC decoding algorithms. In this paper GDL based maximum-likelihood (ML) decoding of Space-Time Block Codes (STBCs) is introduced and a sufficient condition for an STBC to admit low GDL decoding complexity is given. Fast-decoding and multigroup decoding are the two algorithms used in the literature to ML decode STBCs with low complexity. An algorithm which exploits the advantages of both these two is called Conditional ML (CML) decoding. It is shown in this paper that the GDL decoding complexity of any STBC is upper bounded by its CML decoding complexity, and that there exist codes for which the GDL complexity is strictly less than the CML complexity. Explicit examples of two such families of STBCs is given in this paper. Thus the CML is in general suboptimal in reducing the ML decoding complexity of a code, and one should design codes with low GDL complexity rather than low CML complexity.

Generalized distributive law for ML decoding of space-time block codes

The problem of designing good space-time block codes (STBCs) with low maximum-likelihood (ML) decoding complexity has gathered much attention in the literature. All the known low ML decoding complexity techniques utilize the same approach of exploiting either the multigroup decodable or the fast-decodable (conditionally multigroup decodable) structure of a code. We refer to this well-known technique of decoding STBCs as conditional ML (CML) decoding. In this paper, we introduce a new framework to construct ML decoders for STBCs based on the generalized distributive law (GDL) and the factor-graph-based sum-product algorithm. We say that an STBC is fast GDL decodable if the order of GDL decoding complexity of the code, with respect to the constellation size, is strictly less than M-lambda, where lambda is the number of independent symbols in the STBC. We give sufficient conditions for an STBC to admit fast GDL decoding, and show that both multigroup and conditionally multigroup decodable codes are fast GDL decodable. For any STBC, whether fast GDL decodable or not, we show that the GDL decoding complexity is strictly less than the CML decoding complexity. For instance, for any STBC obtained from cyclic division algebras which is not multigroup or conditionally multigroup decodable, the GDL decoder provides about 12 times reduction in complexity compared to the CML decoder. Similarly, for the Golden code, which is conditionally multigroup decodable, the GDL decoder is only half as complex as the CML decoder.

Generalized distributive law for ML decoding of STBCs: further results

The problem of designing good Space-Time Block Codes (STBCs) with low maximum-likelihood (ML) decoding complexity has gathered much attention in the literature. All the known low ML decoding complexity techniques utilize the same approach of exploiting either the multigroup decodable or the fast-decodable (conditionally multigroup decodable) structure of a code. We refer to this well known technique of decoding STBCs as Conditional ML (CML) decoding. In [1], we introduced a framework to construct ML decoders for STBCs based on the Generalized Distributive Law (GDL) and the Factor-graph based Sum-Product Algorithm, and showed that for two specific families of STBCs, the Toepltiz codes and the Overlapped Alamouti Codes (OACs), the GDL based ML decoders have strictly less complexity than the CML decoders. In this paper, we introduce a `traceback' step to the GDL decoding algorithm of STBCs, which enables roughly 4 times reduction in the complexity of the GDL decoders proposed in [1]. Utilizing this complexity reduction from `traceback', we then show that for any STBC (not just the Toeplitz and Overlapped Alamouti Codes), the GDL decoding complexity is strictly less than the CML decoding complexity. For instance, for any STBC obtained from Cyclic Division Algebras that is not multigroup or conditionally multigroup decodable, the GDL decoder provides approximately 12 times reduction in complexity compared to the CML decoder. Similarly, for the Golden code, which is conditionally multigroup decodable, the GDL decoder is only about half as complex as the CML decoder.

The generalized second law of thermodynamics in generalized gravity theories

We investigate the generalized second law of thermodynamics (GSL) in generalized theories of gravity. We examine the total entropy evolution with time including the horizon entropy, the non-equilibrium entropy production, and the entropy of all matter, field and energy components. We derive a universal condition to protect the generalized second law and study its validity in different gravity theories. In Einstein gravity (even in the phantom-dominated universe with a Schwarzschild black hole), Lovelock gravity and braneworld gravity, we show that the condition to keep the GSL can always be satisfied. In f ( R) gravity and scalar-tensor gravity, the condition to protect the GSL can also hold because the temperature should be positive, gravity is always attractive and the effective Newton constant should be an approximate constant satisfying the experimental bounds.

Phantom accretion by black holes and the generalized second law of thermodynamics

The accretion of a phantom fluid with non-zero chemical potential by black holes is discussed with basis on the generalized second law of thermodynamics. For phantom fluids with positive temperature and negative chemical potential we demonstrate that the accretion process is possible, and that the condition guaranteeing the positiveness of the phantom fluid entropy coincides with the one required by the generalized second law. (C) 2010 Elsevier B.V. All rights reserved.

New thought experiment to test the generalized second law of thermodynamics

We propose an extension of the original thought experiment proposed by Geroch, which sparked much of the actual debate and interest on black hole thermodynamics, and show that the generalized second law of thermodynamics is in compliance with it.

Advanced Physical Chemistry Problems (IV), Thermodynamics (2nd Law)

This is a set of P. Chem. problems posed at a slightly higher level than the normal textbook level, for students who are continuing in the study of this subject.

On phantom thermodynamics

The thermodynamic properties of dark energy fluids described by an equation of state parameter omega = p/rho are rediscussed in the context of FRW type geometries. Contrarily to previous claims, it is argued here that the phantom regime omega < -1 is not physically possible since that both the temperature and the entropy of every physical fluids must be always positive definite. This means that one cannot appeal to negative temperature in order to save the phantom dark energy hypothesis as has been recently done in the literature. Such a result remains true as long as the chemical potential is zero. However, if the phantom fluid is endowed with a non-null chemical potential, the phantom field hypothesis becomes thermodynamically consistent, that is, there are macroscopic equilibrium states with T > 0 and S > 0 in the course of the Universe expansion. (C) 2008 Elsevier B.V. All rights reserved.

Thermodynamical description of the interaction between holographic dark energy and dark matter

We present a thermodynamical description of the interaction between holographic dark energy and dark matter. If holographic dark energy and dark matter evolve separately, each of them remains in thermodynamic equilibrium. A small interaction between them may be viewed as a stable thermal fluctuation that brings a logarithmic correction to the equilibrium entropy. From this correction we obtain a physical expression for the interaction which is consistent with phenomenological descriptions and passes reasonably well the observational tests: (c) 2008 Elsevier B.V. All rights reserved.

Consistency of the mass variation formula for black holes accreting cosmological fluids

We address the spherical accretion of generic fluids onto black holes. We show that, if the black hole metric satisfies certain conditions, in the presence of a test fluid it is possible to derive a fully relativistic prescription for the black hole mass variation. Although the resulting equation may seem obvious due to a form of it appearing as a step in the derivation of the Schwarzschild metric, this geometrical argument is necessary to fix the added degree of freedom one gets for allowing the mass to vary with time. This result has applications on cosmological accretion models and provides a derivation from first principles to serve as a basis to the accretion equations already in use in the literature.

Relativistic Archimedes law for fast moving bodies and the general-relativistic resolution of the submarine paradox

We investigate and solve in the context of general relativity the apparent paradox which appears when bodies floating in a background fluid are set in relativistic motion. Suppose some macroscopic body, say, a submarine designed to lie just in equilibrium when it rests (totally) immersed in a certain background fluid. The puzzle arises when different observers are asked to describe what is expected to happen when the submarine is given some high velocity parallel to the direction of the fluid surface. on the one hand, according to observers at rest with the fluid, the submarine would contract and, thus, sink as a consequence of the density increase. on the other hand, mariners at rest with the submarine using an analogous reasoning for the fluid elements would reach the opposite conclusion. The general relativistic extension of the Archimedes law for moving bodies shows that the submarine sinks. As an extra bonus, this problem suggests a new gedankenexperiment for the generalized second law of thermodynamics.

Saltation in wind blown sand

The Boltzmann equation of the sand particle velocity distribution function in wind-blown sand two-phase flow is established based on the motion equation of single particle in air. And then, the generalized balance law of particle property in single phase granular flow is extended to gas-particle two-phase flow. The velocity distribution function of particle phase is expanded into an infinite series by means of Grad's method and the Gauss distribution is used to replace Maxwell distribution. In the case of truncation at the third-order terms, a closed third-order moment dynamical equation system is constructed. The theory is further simplified according to the measurement results obtained by stroboscopic photography in wind tunnel tests.

The Cache Inference Problem and its Application to Content and Request Routing

In many networked applications, independent caching agents cooperate by servicing each other's miss streams, without revealing the operational details of the caching mechanisms they employ. Inference of such details could be instrumental for many other processes. For example, it could be used for optimized forwarding (or routing) of one's own miss stream (or content) to available proxy caches, or for making cache-aware resource management decisions. In this paper, we introduce the Cache Inference Problem (CIP) as that of inferring the characteristics of a caching agent, given the miss stream of that agent. While CIP is insolvable in its most general form, there are special cases of practical importance in which it is, including when the request stream follows an Independent Reference Model (IRM) with generalized power-law (GPL) demand distribution. To that end, we design two basic "litmus" tests that are able to detect LFU and LRU replacement policies, the effective size of the cache and of the object universe, and the skewness of the GPL demand for objects. Using extensive experiments under synthetic as well as real traces, we show that our methods infer such characteristics accurately and quite efficiently, and that they remain robust even when the IRM/GPL assumptions do not hold, and even when the underlying replacement policies are not "pure" LFU or LRU. We exemplify the value of our inference framework by considering example applications.