| 1. |
- Andersson, Joel, et al.
(författare)
-
On the Theorem of Uniform Recovery of Random Sampling Matrices
- 2014
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 60:3, s. 1700-1710
-
Tidskriftsartikel (refereegranskat)abstract
- We consider two theorems from the theory of compressive sensing. Mainly a theorem concerning uniform recovery of random sampling matrices, where the number of samples needed in order to recover an s-sparse signal from linear measurements (with high probability) is known to be m greater than or similar to s(ln s)(3) ln N. We present new and improved constants together with what we consider to be a more explicit proof. A proof that also allows for a slightly larger class of m x N-matrices, by considering what is called effective sparsity. We also present a condition on the so-called restricted isometry constants, delta s, ensuring sparse recovery via l(1)-minimization. We show that delta(2s) < 4/root 41 is sufficient and that this can be improved further to almost allow for a sufficient condition of the type delta(2s) < 2/3.
|
|
| 2. |
- Austrin, Per, et al.
(författare)
-
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
- 2014
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 60:10, s. 6636-6645
-
Tidskriftsartikel (refereegranskat)abstract
- We present a simple deterministic gap-preserving reduction from SAT to the minimum distance of code problem over F-2. We also show how to extend the reduction to work over any fixed finite field. Previously, a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly nontrivial coding theoretic constructions, whereas our reduction is elementary. As an additional feature, our reduction gives hardness within a constant factor even for asymptotically good codes, i.e., having constant positive rate and relative distance. Previously, it was not known how to achieve a deterministic reduction for such codes.
|
|
| 3. |
- Austrin, Per, 1981-, et al.
(författare)
-
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
- 2018
-
Ingår i: IEEE Transactions on Information Theory. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 0018-9448 .- 1557-9654. ; 64:2, s. 1368-1373
-
Tidskriftsartikel (refereegranskat)abstract
- Two sets of 0-1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.
|
|
| 4. |
- Bassi, German, et al.
(författare)
-
The Wiretap Channel With Generalized Feedback : Secure Communication and Key Generation
- 2019
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 65:4, s. 2213-2233
-
Tidskriftsartikel (refereegranskat)abstract
- It is a well-known fact that feedback does not increase the capacity of point-to-point memoryless channels, however, its effect in secure communications is not fully understood yet. In this paper, an achievable scheme for the wiretap channel with generalized feedback is presented. This scheme, which uses the feedback signal to generate a shared secret key between the legitimate users, encrypts the message to be sent at the bit level. New capacity results for a class of channels are provided, as well as some new insights into the secret key agreement problem. Moreover, this scheme recovers previously reported rate regions from the literature, and thus it can be seen as a generalization that unifies several results in the field.
|
|
| 5. |
- Björnson, Emil, et al.
(författare)
-
Massive MIMO Systems With Non-Ideal Hardware : Energy Efficiency, Estimation, and Capacity Limits
- 2014
-
Ingår i: IEEE Transactions on Information Theory. - : IEEE Press. - 0018-9448 .- 1557-9654. ; 60:11, s. 7112-7139
-
Tidskriftsartikel (refereegranskat)abstract
- The use of large-scale antenna arrays can bring substantial improvements in energy and/or spectral efficiency to wireless systems due to the greatly improved spatial resolution and array gain. Recent works in the field of massive multiple-input multiple-output (MIMO) show that the user channels decorrelate when the number of antennas at the base stations (BSs) increases, thus strong signal gains are achievable with little interuser interference. Since these results rely on asymptotics, it is important to investigate whether the conventional system models are reasonable in this asymptotic regime. This paper considers a new system model that incorporates general transceiver hardware impairments at both the BSs (equipped with large antenna arrays) and the single-antenna user equipments (UEs). As opposed to the conventional case of ideal hardware, we show that hardware impairments create finite ceilings on the channel estimation accuracy and on the downlink/uplink capacity of each UE. Surprisingly, the capacity is mainly limited by the hardware at the UE, while the impact of impairments in the large-scale arrays vanishes asymptotically and interuser interference (in particular, pilot contamination) becomes negligible. Furthermore, we prove that the huge degrees of freedom offered by massive MIMO can be used to reduce the transmit power and/or to tolerate larger hardware impairments, which allows for the use of inexpensive and energy-efficient antenna elements.
|
|
| 6. |
- Bordenave, Charles, et al.
(författare)
-
Asymptotic Stability Region of Slotted Aloha
- 2012
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 58:9, s. 5841-5855
-
Tidskriftsartikel (refereegranskat)abstract
- We analyze the stability of standard, buffered, slotted-Aloha systems. Specifically, we consider a set of users, each equipped with an infinite buffer. Packets arrive into user i's buffer according to some stationary ergodic Markovian process of intensity lambda(i). At the beginning of each slot, if user i has packets in its buffer, it attempts to transmit a packet with fixed probability p(i) over a shared resource/channel. The transmission is successful only when no other user attempts to use the channel. The stability of such systems has been open since their very first analysis in 1979 by Tsybakov and Mikhailov. In this paper, we propose an approximate stability condition that is provably exact when the number of users grows large. We provide theoretical evidence and numerical experiments to explain why the proposed approximate stability condition is extremely accurate even for systems with a restricted number of users (even two or three).
|
|
| 7. |
- Brännström, Fredrik, 1974, et al.
(författare)
-
Classification of Unique Mappings for 8PSK Based on Bit-Wise Distance Spectra
- 2009
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 55:3, s. 1131-1145
-
Tidskriftsartikel (refereegranskat)abstract
- The performance of bit-interleaved coded modulation (BICM) with (or without) iterative decoding (ID) is significantly influenced by the mapping of bits to the symbol constellation. Our main objective in this paper is to develop a systematic design approach for BICM-ID schemes, ensuring the best possible performance with iterative decoding. Although useful mappings for BICM-ID have been found based on various search strategies, no attempt has been made to systematically enumerate and classify all unique mappers for a given constellation. As the basis for a systematic enumeration and classification, we define the average bit-wise distance spectrum for a mapping from bits to symbols. Different bit-wise distance spectra are derived assuming no prior information or full prior information, respectively. The bit-wise distance spectra determine corresponding bit-wise error probability and bit-wise mutual information. The latter allows us to use the classification of mappings with unique bit-wise distance spectra to also classify mappings with unique extremal points in the corresponding extrinsic information transfer (EXIT) curves. As an example of our approach, we classify 8PSK mappings into 86 classes of unique mappings according to bit-wise distance spectra. The classification can be used to significantly reduce the complexity of the search for suitable mappers for BICM-ID. For 8PSK and a given encoder, only 86 different mappings need to be, investigated. As examples of the systematic design approach, the best 8PSK mappings for minimizing the convergence threshold are found for concatenation with the rate 1/2 (5, 7)(8) and (133, 171)(8) convolutional codes, and the rate 1/2 UMTS turbo code with identical constituent convolutional codes (15/13)(8).
|
|
| 8. |
- Brännström, Fredrik, 1974, et al.
(författare)
-
Convergence analysis and optimal scheduling for multiple concatenated codes
- 2005
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 51:9, s. 3354-3364
-
Tidskriftsartikel (refereegranskat)abstract
- An interesting practical consideration for decoding of serial or parallel concatenated codes with more than two components is the determination of the lowest complexity component decoder schedule which results in convergence. This correspondence presents an algorithm that finds such an optimal decoder schedule. A technique is also given for combining and projecting a series of three-dimensional extrinsic information transfer (EXIT) functions onto a single two-dimensional EXIT chart. This is a useful technique for visualizing the convergence threshold for multiple concatenated codes and provides a design tool for concatenated codes with more than two components.
|
|
| 9. |
- Brännström, Fredrik, 1974, et al.
(författare)
-
Optimal Puncturing Ratios and Energy Allocation for Multiple Parallel Concatenated Codes
- 2009
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 55:5, s. 2062-2077
-
Tidskriftsartikel (refereegranskat)abstract
- We propose a systematic design framework for optimal, low-complexity punctured multiple parallel concatenated codes (MPCCs), based on minimizing the convergence threshold using extrinsic information transfer (EXIT) charts. As the convergence threshold is related to the area between the two EXIT curves, the corresponding optimization problem is equivalent to a curve-fitting problem. The EXIT curves are determined by the respective EXIT functions of the constituents, which can be conveniently shaped through the use of random puncturing and unequal energy allocations across parallel coding streams. The design task is therefore to find the optimal combination of constituents, puncturing ratios, and energy allocation for matching the EXIT curves. A search over all rate-one convolutional codes of memory length four or less is performed, identifying 98 classes of codes with unique EXIT functions out of a total of 310 codes. Low-complexity MPCCs with up to four constituents are found, where the convergence thresholds are observed to be within 0.1 dB or less of the fundamental minimum signal-to-noise ratio (SNR) corresponding to the binary phase-shift keying (BPSK) capacity for code rates 1/3
|
|
| 10. |
- Bukh, Boris, et al.
(författare)
-
An Improved Bound on the Fraction of Correctable Deletions
- 2017
-
Ingår i: IEEE Transactions on Information Theory. - : IEEE. - 0018-9448 .- 1557-9654. ; 63:1, s. 93-103
-
Tidskriftsartikel (refereegranskat)abstract
- We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k >= 2, we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1 - (2/(k + root k)). In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(root 2+1) = root 2-1 approximate to 0.414. Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1 - Theta (1/root k), and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for k-ary codes as 1 - Theta (1/k), since 1 - 1/k is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between (root 2 - 1) and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question.
|
|
