The Experts below are selected from a list of 6552 Experts worldwide ranked by ideXlab platform
Richard Laver - One of the best experts on this subject based on the ideXlab platform.
-
the free one generated left Distributive algebra basics and a simplified proof of the division algorithm
Open Mathematics, 2013Co-Authors: Richard Laver, Sheila K MillerAbstract:The left Distributive Law is the Law a· (b· c) = (a·b) · (a· c). Left Distributive algebras have been classically used in the study of knots and braids, and more recently free left Distributive algebras have been studied in connection with large cardinal axioms in set theory. We provide a survey of results on the free left Distributive algebra on one generator, A, and a new, simplified proof of the existence of a normal form for terms in A. Topics included are: the confluence of A, the linearity of the iterated left division ordering
-
left division in the free left Distributive algebra on one generator
Journal of Pure and Applied Algebra, 2011Co-Authors: Richard Laver, Sheila K MillerAbstract:Abstract Let A be the free algebra on one generator satisfying the left Distributive Law a ( b c ) = ( a b ) ( a c ) . Using a division algorithm for elements of an extension P of A , we prove some facts about left division in A , one consequence of which is a conjecture of J. Moody: If a , b , c , d ∈ A , a b = c d , a and b have no common left divisors, and c and d have no common left divisors, then a = c and b = d .
-
a division algorithm for the free left Distributive algebra
arXiv: Logic, 1993Co-Authors: Richard LaverAbstract:The normal form theorem, proved in R. Laver, On the left Distributive Law and the freeness of an algebra of elementary embeddings, Advances in Mathematics 91 (1992), 209-231, for the free algebra $\Cal A$ on one generator $x$ satisfying the left Distributive Law $a(bc) = (ab)(ac)$ is extended by showing that members of $\Cal A$ can be put into a "division form."
-
the left Distributive Law and the freeness of an algebra of elementary embeddings
Advances in Mathematics, 1992Co-Authors: Richard LaverAbstract:The left Distributive Law for a single binary operation is the Law a(&) = (&)(a~). It has been studied in universal algebra (Stein [S], Kepka and Nemec [KN], Kepka [Kl, K2]; see also Jezek et al. [JKN] for a bibliography on the two-sided Distributive Law) and it has been studied more recently by set theorists because of its connection with elementary embeddings. For E, a limit ordinal let 6;. be the collection of all j: I’, -+ I’,, j an elementary embedding of (V,, E) into itself, j not the identity. Then the existence of a 3. such that c$;. # @ is a large cardinal axiom (see Gaifman [G] and Kanamori et ul. [KRS]). For Jo&;, let K~= cr(j), the critical point of j, and ti,+ i =j(~,~). Then 1 must equal sup(~,, : II
Lakshmi Natarajan - One of the best experts on this subject based on the ideXlab platform.
-
generalized Distributive Law for ml decoding of space time block codes
IEEE Transactions on Information Theory, 2013Co-Authors: Lakshmi Natarajan, B S RajanAbstract: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 M, is strictly less than Mλ, where λ 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
International Symposium on Information Theory, 2012Co-Authors: Lakshmi Natarajan, Sundar B RajanAbstract: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.
-
generalized Distributive Law for ml decoding of stbcs
2011Co-Authors: Lakshmi Natarajan, Pavan K Srinath, Sundar B RajanAbstract: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
arXiv: Information Theory, 2011Co-Authors: Lakshmi Natarajan, Sundar B RajanAbstract: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 is strictly less than M^l, where l is the number of independent symbols in the STBC, and M is the constellation size. 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.
Sheila K Miller - One of the best experts on this subject based on the ideXlab platform.
-
the free one generated left Distributive algebra basics and a simplified proof of the division algorithm
Open Mathematics, 2013Co-Authors: Richard Laver, Sheila K MillerAbstract:The left Distributive Law is the Law a· (b· c) = (a·b) · (a· c). Left Distributive algebras have been classically used in the study of knots and braids, and more recently free left Distributive algebras have been studied in connection with large cardinal axioms in set theory. We provide a survey of results on the free left Distributive algebra on one generator, A, and a new, simplified proof of the existence of a normal form for terms in A. Topics included are: the confluence of A, the linearity of the iterated left division ordering
-
left division in the free left Distributive algebra on one generator
Journal of Pure and Applied Algebra, 2011Co-Authors: Richard Laver, Sheila K MillerAbstract:Abstract Let A be the free algebra on one generator satisfying the left Distributive Law a ( b c ) = ( a b ) ( a c ) . Using a division algorithm for elements of an extension P of A , we prove some facts about left division in A , one consequence of which is a conjecture of J. Moody: If a , b , c , d ∈ A , a b = c d , a and b have no common left divisors, and c and d have no common left divisors, then a = c and b = d .
Sundar B Rajan - One of the best experts on this subject based on the ideXlab platform.
-
generalized Distributive Law for ml decoding of stbcs further results
International Symposium on Information Theory, 2012Co-Authors: Lakshmi Natarajan, Sundar B RajanAbstract: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.
-
generalized Distributive Law for ml decoding of stbcs
2011Co-Authors: Lakshmi Natarajan, Pavan K Srinath, Sundar B RajanAbstract: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
arXiv: Information Theory, 2011Co-Authors: Lakshmi Natarajan, Sundar B RajanAbstract: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 is strictly less than M^l, where l is the number of independent symbols in the STBC, and M is the constellation size. 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.
R J Mceliece - One of the best experts on this subject based on the ideXlab platform.
-
the generalized Distributive Law and free energy minimization
2001Co-Authors: Srinivas M Aji, R J McelieceAbstract:In an important recent paper, Yedidia, Freeman, and Weiss [7] showed that there is a close connection between the belief propagation algorithm for probabilistic inference and the Bethe-Kikuchi approximation to the variational free energy in statistical physics. In this paper, we will recast the YFW results in the context of the “generalized Distributive Law” [1] formulation of belief propagation. Our main result is that if the GDL is applied to junction graph, the fixed points of the algorithm are in one-to-one correspondence with the stationary points of a certain Bethe-Kikuchi free energy. If the junction graph has no cycles, the BK free energy is convex and has a unique stationary point, which is a global minimum. On the other hand, if the junction graph has cycles, the main result at least shows that the GDL is trying to do something sensible.
-
the generalized Distributive Law
IEEE Transactions on Information Theory, 2000Co-Authors: Srinivas M Aji, R J McelieceAbstract:We discuss a general message passing algorithm, which we call the generalized Distributive Law (GDL). The GDL is a synthesis of the work of many authors in information theory, digital communications, signal processing, statistics, and artificial intelligence. It includes as special cases the Baum-Welch algorithm, the fast Fourier transform (FFT) on any finite Abelian group, the Gallager-Tanner-Wiberg decoding algorithm, Viterbi's algorithm, the BCJR algorithm, Pearl's "belief propagation" algorithm, the Shafer-Shenoy probability propagation algorithm, and the turbo decoding algorithm. Although this algorithm is guaranteed to give exact answers only in certain cases (the "junction tree" condition), unfortunately not including the cases of GTW with cycles or turbo decoding, there is much experimental evidence, and a few theorems, suggesting that it often works approximately even when it is not supposed to.