Unifying information theory and digital communication through the language of lattice codes, this book provides a detailed overview for students, researchers and industry practitioners. It covers classical work by lea...
详细信息
ISBN:
(数字)9781139989275
ISBN:
(纸本)9780521766982
Unifying information theory and digital communication through the language of lattice codes, this book provides a detailed overview for students, researchers and industry practitioners. It covers classical work by leading researchers in the field of lattice codes and complementary work on dithered quantization and infinite constellations, and then introduces the more recent results on 'algebraic binning' for side-information problems, and linear/lattice codes for networks. It shows how high dimensional lattice codes can close the gap to the optimal information theoretic solution, including the characterisation of error exponents. The solutions presented are based on lattice codes, and are therefore close to practical implementations, with many advanced setups and techniques, such as shaping, entropy-coding, side-information and multi-terminal systems. Moreover, some of the network setups shown demonstrate how lattice codes are potentially more efficient than traditional random-coding solutions, for instance when generalising the framework to Gaussian networks.
The aim of this paper is to describe a new class of problems and some new results in coding theory arising from the analysis of the composition and functionality of the genetic code. The major goal of the proposed wor...
详细信息
ISBN:
(纸本)0780387201
The aim of this paper is to describe a new class of problems and some new results in coding theory arising from the analysis of the composition and functionality of the genetic code. The major goal of the proposed work is to initiate research on investigating possible connections between the regulatory network of gene interactions (RNGI) and the proofreading (error-control) mechanism of the processes of the central dogma of genetics. New results include establishing a direct relationship between Boolean Network (BN) Models of RNGI and Gallager's LDPC decoding algorithms. The proposed research topics and described results are expected to have a two-fold impact on coding theory and genetics research. Firstly, they may provide a different setting in which to analyze standard LDPC decoding algorithms, by using dynamical systems and Boolean function theory. Secondly, they may be of use in establishing deeper relationships between the DNA proofreading mechanism, RNGIs, as well as their joint influence on the development and possible treatment of genetic diseases like cancer.
This book is tailored to fulfil the requirements in the area of the signal processing in communication systems. The book contains numerous examples, solved problems and exercises to explain the methodology of Fourier ...
详细信息
ISBN:
(数字)9781608058303
ISBN:
(纸本)9781608058310
This book is tailored to fulfil the requirements in the area of the signal processing in communication systems. The book contains numerous examples, solved problems and exercises to explain the methodology of Fourier Series, Fourier Analysis, Fourier Transform and properties, Fast Fourier Transform FFT, Discrete Fourier Transform DFT and properties, Discrete Cosine Transform DCT, Discrete Wavelet Transform DWT and Contourlet Transform CT. The book is characterized by three directions, the communication theory and signal processing point of view, the mathematical point of view and utility computer programs. The contents of this book include chapters in communication system and signals, Fourier Series and Power Spectra, Fourier Transform and Energy Spectra, Fourier Transform and Power Spectra, Correlation Function and Spectral Density, Signal Transmission and Systems, Hilbert Transform, Narrow Band-Pass Signals and Systems and Numerical Computation of Transform coding. This book is intended for undergraduate students in institutes, colleges, universities and academies who want to specialize in the field of communication systems and signal processing. The book will also be very useful to engineers of graduate and post graduate studies as well as researchers in research centers since it contains a great number of mathematical operations that are considered important in research results.
We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n-party protocol that takes R rounds assuming noiseless communication, the goal is to find a coding sche...
详细信息
We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n-party protocol that takes R rounds assuming noiseless communication, the goal is to find a coding scheme that takes R rounds and computes the same function with high probability even when the communication is noisy, while maintaining a constant asymptotic rate, i.e., while keeping lim infn, R.8 R/ R positive. Rajagopalan and Schulman (STOC'94) were the first to consider this question, and provided a coding scheme with rate O(1/ log(d + 1)), where d is the maximal degree in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is O(1/ log n), which tends to 0 as n tends to infinity. We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if a (d-regular) network has mixing time m, then there exists an efficient coding scheme with rate O(1/ m3 logm). This implies a constant rate coding scheme for any n-party protocol over a d-regular network with a constant mixing time, and in particular for random graphs with n vertices and degrees nO(1).
The distance distribution of a code is the vector whose ith entry is the number of pairs of codewords with distance i. We investigate the structure of the distance distribution for cyclic orbit codes, which are subspa...
详细信息
The distance distribution of a code is the vector whose ith entry is the number of pairs of codewords with distance i. We investigate the structure of the distance distribution for cyclic orbit codes, which are subspace codes generated by the action of F-qn* on an F-q-subspace U of F-qn. Note that F-qn* is a Singer cycle in the general linear group of all F-q-automorphisms of F-qn. We show that for full-length orbit codes with maximal possible distance the distance distribution depends only on q,n, and the dimension of U. For full-length orbit codes with lower minimum distance, we provide partial results towards a characterization of the distance distribution, especially in the case that any two codewords intersect in a space of dimension at most 2. Finally, we briefly address the distance distribution of a union of full-length orbit codes with maximum distance.
This paper describes the implementation of polycomp, a open-sourced, publicly available program for compressing one-dimensional data series in tabular format. The program is particularly suited for compressing smooth,...
详细信息
This paper describes the implementation of polycomp, a open-sourced, publicly available program for compressing one-dimensional data series in tabular format. The program is particularly suited for compressing smooth, noiseless streams of data like pointing information, as one of the algorithms it implements applies a combination of least squares polynomial fitting and discrete Chebyshev transforms that is able to achieve a compression ratio C-r up to approximate to 40 in the examples discussed in this work. This performance comes at the expense of a loss of information, whose upper bound is configured by the user. I show two areas in which the usage of polycomp is interesting. In the first example, I compress the ephemeris table of an astronomical object (Ganymede), obtaining C-r approximate to 20, with a compression error on the x, y, z coordinates smaller than 1 m. In the second example, I compress the publicly available timelines recorded by the Low Frequency Instrument (LFI), an array of microwave radiometers onboard the ESA Planck spacecraft. The compression reduces the needed storage from similar to 6.5 TB to approximate to 0.75 TB (C-r approximate to 9), thus making them small enough to be kept in a portable hard drive. (C) 2016 Elsevier B.V. All rights reserved.
The Delsarte linear program is used to bound the size of codes given their block length n and minimal distance d by taking a linear relaxation from codes to quasicodes. We study for which values of (n, d) this linear ...
详细信息
The Delsarte linear program is used to bound the size of codes given their block length n and minimal distance d by taking a linear relaxation from codes to quasicodes. We study for which values of (n, d) this linear program has a unique optimum: while we show that it does not always have a unique optimum, we prove that it does if d > n/2 or if d <= 2. Introducing the Krawtchouk decomposition of a quasicode, we prove there exist optima to the (n, 2e) and (n - 1, 2e - 1) linear programs that have essentially identical Krawtchouk decompositions, revealing a parity phenomenon among the Delsarte linear programs. We generalize the notion of extending and puncturing codes to quasicodes, from which we see that this parity relationship is given by extending/puncturing. We further characterize these pairs of optima, in particular demonstrating that they exhibit a symmetry property, effectively halving the number of decision variables.
In this paper, we give several new constructions of write-once-memory (WOM) codes. The novelty in our constructions is the use of the so-called Wozencraft ensemble of linear codes. Specifically, we obtain the followin...
详细信息
In this paper, we give several new constructions of write-once-memory (WOM) codes. The novelty in our constructions is the use of the so-called Wozencraft ensemble of linear codes. Specifically, we obtain the following results. We give an explicit construction of a two-write WOM code that approaches capacity, over the binary alphabet. More formally, for every epsilon > 0, 0 < p < 1, and n = (1/epsilon)(O(1/p epsilon)), we give a construction of a two-write WOM code of length n and capacity H(p) + 1 - p - epsilon. Since the capacity of a two-write WOM code is max(p)(H(p) + 1 - p), we get a code that is epsilon-close to capacity. Furthermore, encoding and decoding can be done in time O(n(2) . poly(log n)) and time O(n . poly(log n)), respectively, and in logarithmic space. In addition, we exhibit an explicit randomized encoding scheme of a two-write capacity-achieving WOM code of block length polynomial in 1/epsilon (again, epsilon is the gap to capacity), with a polynomial time encoding and decoding. We obtain a new encoding scheme for three-write WOM codes over the binary alphabet. Our scheme achieves rate 1.809 - epsilon, when the block length is exp(1/epsilon). This gives a better rate than what could be achieved using previous techniques. We highlight a connection to linear seeded extractors for bit-fixing sources. In particular, we show that obtaining such an extractor with seed length O(log n) can lead to improved parameters for two-write WOM codes. We then give an application of existing constructions of extractors to the problem of designing encoding schemes for memory with defects.
暂无评论