We address the design and optimization of real-world-suitable hybrid precoders for multi-user wideband sub-terahertz (sub- THz) communications. We note that the conventional fully connected true-time delay (TTD)-based architecture is impractical because there is no room for the required large num-ber of analog signal combiners in the circuit board. Additionally, analog signal combiners incur significant signal power loss. These limitations are often overlooked in sub- THz research. To overcome these issues, we study a non-overlapping subarray architecture that eliminates the need for analog combiners. We extend the conventional single-user assumption by formulating an optimization problem to maximize the minimum data rate for simultaneously served users. This complex optimization problem is divided into two sub-problems. The first sub-problem aims to ensure a fair subarray allocation for all users and is solved via a continuous domain relaxation technique. The second sub-problem deals with practical TTD device constraints on range and resolution to maximize the sub array gain and is resolved by shifting to the phase domain. Our simulation results highlight significant performance gain for our real-world-ready TTD-based hybrid precoders.

A key constraint that limits the implementation of blockchain in Internet of Things (IoT) is its large storage requirement resulting from the fact that each blockchain node has to store the entire blockchain. This increases the burden on blockchain nodes, and increases the communication overhead for new nodes joining the network since they have to copy the entire blockchain. In order to reduce storage requirements without compromising on system security and integrity, coded blockchains, based on error correcting codes with fixed rates and lengths, have been recently proposed. This approach, however, does not fit well with dynamic IoT networks in which nodes actively leave and join. In such dynamic blockchains, the existing coded blockchain approaches lead to high-communication overheads for new joining nodes and may have high-decoding failure probability. This article proposes a rateless coded blockchain with coding parameters adjusted to network conditions. Our goals are to minimize both the storage requirement at each blockchain node and the communication overhead for each new joining node, subject to a target decoding failure probability. We evaluate the proposed scheme in the context of real-world Bitcoin blockchain and show that both storage and communication overhead are reduced by 99.6% with a maximum 10−12 decoding failure probability.

For achieving long-distance quantum communication, Quantum Repeaters (QRs) have to be used, with commu-nication range and reliability increased by using intermediate stations. The physical requirements of second generation QRs may be achievable in the near future. They use Quantum Error Correction Codes (QECC) to protect logical qubits against environmental interaction using physical redundancy. In this work, we study the types of errors that can corrupt quantum codewords in intermediate stations. Our studies show that the errors are distance-dependent, and also consist of correlated errors and biased errors. To mitigate this error model, we use non-symmetric CSS codes as well as mirrored structure coding. We show that using non-symmetric CSS codes results in better performance. Also, we prove the logical CZ gate transversality of the mirrored structure coding. The effectiveness of the proposed methods is verified by numerical simulations.

We investigate Cell-Free massive MIMO networks, where each access point (AP) is equipped with a hybrid transceiver, reducing the complexity and cost compared to a fully digital transceiver. Asymptotic approximations for the spectral efficiency are derived for uplink and downlink. Capitalizing on these expressions, a max-min problem is formulated enabling us to optimize the (i) analog beamformer at the APs and (ii) pilot assignment. Simulations show that the optimization of these variables substantially increases the minimum user throughput.

Cell-Free Massive Multiple-input Multiple-output (mMIMO) consists of many access points (APs) in a coverage area that jointly serve the users. These systems can significantly reduce the interference among the users compared to conventional MIMO networks and so enable higher data rates and a larger coverage area. However, Cell-Free mMIMO systems face multiple practical challenges such as the high complexity and power consumption of the APs’ analog front-ends. Motivated by prior works, we address these issues by considering a low complexity hybrid beamforming framework at the APs in which each AP has a limited number of RF-chains to reduce power consumption, and the analog combiner is designed only using the large-scale statistics of the channel to reduce the system’s complexity. We provide closed-form expressions for the signal to interference and noise ratio (SINR) of both uplink and downlink data transmission with accurate random matrix approximations. Also, based on the existing literature, we provide a power optimization algorithm that maximizes the minimum SINR of the users for uplink scenario. Through several simulations, we investigate the accuracy of the derived random matrix approximations, tradeoff between the 95% outage data rate and the number of RF-chains, and the impact of power optimization. We observe that the derived approximations accurately follow the exact simulations and that in uplink scenario while using MMSE combiner, power optimization does not improve the performance much.

We propose a partial cooperative zero-forcing (PCZF) decoding scheme for the uplink cell-free massive MIMO system, wherein the neighboring access points (APs) around each user equipment (UE) share the channel state information (CSI) and jointly suppress the interference using the zero-forcing technique. Using asymptotic analysis, we derive a closed-form asymptotic expression for a lower bound on the achievable rates. Considering the unique and complex form of the achievable rates, we propose power control schemes according to two criteria. The first criterion is to maximize the minimum achievable rate. For this criterion, we propose a target-SINR-tracking (TST)-based bisection algorithm. Since the power control update functions are standard interference functions, the TST-based bisection method always converges to the optimal solution. The second criterion is to maximize the sum rate, for which we propose two power control algorithms: 1) randomization and scaling algorithm (RSA) and 2) fractional programming algorithm (FPA). In each iteration of the RAS algorithm, we first exploit the randomization technique to transform the sum-rate maximization problem into a series of power minimization problems, and then improve the sum rate by scaling. In the FP algorithm, we derive a lower bound on the sum rate, and then propose an iterative approach based on the Lagrangian dual transform and fractional programming to maximize the sum-rate lower bound. Numerical results validate the theoretical analysis and verify the efficiency of the proposed power control algorithms.

We investigate the activity detection and channel estimation issues for cell-free Internet of Things (IoT) networks with massive random access. In each time slot, only partial devices are active and communicate with neighboring access points (APs) using non-orthogonal random pilot sequences. Different from the centralized processing in cellular networks, the activity detection and channel estimation in cell-free IoT is more challenging due to the distributed and user-centric architecture. We propose a two-stage approach to detect the random activities of devices and estimate their channel states. In the first stage, the activity of each device is jointly detected by its adjacent APs based on the vector approximate message passing (Vector AMP) algorithm. In the second stage, each AP re-estimates the channel using the linear minimum mean square error (LMMSE) method based on the detected activities to improve the channel estimation accuracy. We derive closed-form expressions for the activity detection error probability and the mean-squared channel estimation errors for a typical device. Finally, we analyze the performance of the entire cell-free IoT network in terms of coverage probability. Simulation results validate the derived closed-form expressions and show that the cell-free IoT significantly outperforms the collocated massive MIMO and small-cell schemes in terms of coverage probability.

We investigate the feasibility of using Massive MIMO to support URLLC in both coherence interval based and 3GPP compliant pilot settings. We consider grant-free uplink transmission with MMSE receiver and adopt 3GPP channel models. In the coherence interval based pilot setting, by extensive system level simulations, we find that using a Massive MIMO base station with 128 antennas and MMSE receiver, URLLC requirements can be achieved in Urban Macro (UMa) Non-Line of Sight (NLoS) with orthogonal pilots and Neyman-Pearson detector. However, in the 3GPP compliant pilot setting, even by using the covariance matrix of Physical Resource Block (PRB) subcarriers for active UE detection and channel estimation as well as open-loop power control, we find that URLLC requirements are still challenging to achieve due to the insufficient pilot length and pilot symbol location regulations in a PRB.

We investigate the long-term scheduling and power control scheme for a wirelessly powered cell-free Internet-of-Things (IoT) network which consists of distributed access points (APs) and a large number of sensors. In each time slot, a subset of sensors is scheduled for uplink data transmission or downlink power transfer. Through asymptotic analysis, we obtain closed-form expressions for the harvested energy and the achievable rates that are independent of random pilots. Then, using these expressions, we formulate a long-term scheduling and power control problem to maximize the minimum time-average achievable rate among all sensors while maintaining the battery state of each sensor higher than a predefined minimum level. Using Lyapunov optimization, the transmission mode, the active sensor set, and the power control coefficients for each time slot are jointly determined. Finally, simulation results validate the accuracy of our derived closed-form expressions and reveal that the minimum time-average achievable rate is boosted significantly by the proposed scheme compared with the simple greedy transmission scheme.

An Internet-of-Things (IoT) system supports a massive number of IoT devices wirelessly. We show how to use cell-free (CF) massive multiple input and multiple output (MIMO) to provide a scalable and energy-efficient IoT system. We employ optimal linear estimation with random pilots to acquire channel state information (CSI) for MIMO precoding and decoding. In the uplink (UL), we employ optimal linear decoder and utilize random matrix (RM) theory to obtain two accurate signal-to-interference plus noise ratio (SINR) approximations involving only large-scale fading coefficients. We derive several max–min type power control algorithms based on both exact SINR expression and RM approximations. Next we consider the power control problem for downlink (DL) transmission. To avoid solving a time-consuming quasiconcave problem that requires repeat tests for the feasibility of a second-order cone programming (SOCP) problem, we develop a neural network (NN) aided power control algorithm that results in 30 times reduction in computation time. This power control algorithm leads to scalable CF Massive MIMO networks in which the amount of computations conducted by each access point (AP) does not depend on the number of network APs. Both UL and DL power control algorithms allow visibly improve the system spectral efficiency (SE) and, more importantly, lead to multifold improvements in energy efficiency (EE), which is crucial for IoT networks.

Non-cooperative cellular massive MIMO, combined with power control, is known to lead to significant improvements in per-user throughput compared with conventional LTE technology. In this paper, we investigate further refinements to massive MIMO, first, in the form of three-fold sectorization, and second, coordinated multi-point operation (with and without sectorization), in which the three base stations cooperate in the joint service of their users. For these scenarios, we analyze the downlink performance for both maximum-ratio and zero-forcing precoding and derive closed-form lower-bound expressions on the achievable rate of the users. These expressions are then used to formulate power optimization problems with two throughput fairness criteria:${i}$) network-wide max-min fairness, andii) per-cell max-min fairness. Furthermore, we provide centralized and decentralized power control strategies to optimize the transmit powers in the network. We demonstrate that employing sectorized antenna elements mitigates the detrimental effects of pilot contamination by rejecting a portion of interfering pilots in the spatial domain during channel estimation phase. Simulation results with practical sectorized antennas reveal that sectorization and multi-point coordination combined with sectorization lead to more than$1.7\times $and$2.6\times $improvements in the 95%-likely per-user throughput, respectively.

We consider a wirelessly powered Internet of Things (IoT) based on cell-free massive MIMO with energy harvesting. In such a system, during the downlink phase, the sensors harvest radio-frequency (RF) energy emitted by the distributed access points (APs). During the uplink phase, sensors transmit data to the APs using the harvested energy. We assume that single antenna sensors send uplink pilots in order to allow APs to detect active users and estimate their channel coefficients. We assume that each AP is equipped with N ≥ 1 antennas and uses the linear minimum mean square error (LMMSE) channel estimation. Through an asymptotic analysis, we derive closedform approximations for the variance of the LMMSE channel coefficient estimates, the amount of harvested energy, and the achievable rates for the uplink data transmission. We next use these expressions to jointly optimize the charging duration and uplink and downlink power control coefficients to minimize the total transmit energy consumptions of APs and sensors, which is crucially important for IoT sensors. Simulation results verify the accuracy of the obtained expressions, and shows that significant gains in energy efficiency can be achieved by the proposed optimization algorithms.

We study internet of things (IoT) systems supported by cell-free (CF) massive MIMO (mMIMO) with optimal linear channel estimation. For the uplink, we consider optimal linear MIMO receiver and obtain an uplink SINR approximation involving only large-scale fading coefficients using random matrix (RM) theory. Using this approximation we design several max-min power control algorithms that incorporate power and rate weighting coefficients to achieve a target rate with high energy efficiency. For the downlink, we consider maximum ratio (MR) beamforming. Instead of solving a complex quasi-concave problem for downlink power control, we employ a neural network (NN) technique to obtain comparable power control with around 30 times reduction in computation time. For large networks we proposed a different NN based power control algorithm. This algorithm is sub-optimal, but its big advantage is that it is scalable.

We consider the probability of decoding error, equivalently the fidelity, of finite length quantum codes assuming quantum information transmission via qubit erasure channel. First, we obtain an analytical expression on this probability via combinatorial invariants of quantum codes. Next, we derive a generalization of the MacWilliams identities for those invariants and use them to formulate a linear programming optimization problem, which allows us to obtain lower bounds on the number of unrecoverable sets of i erasures and the probability of decoding error. Our example shows that the obtain bounds can be very tight. Next, we derive upper (achievability) bounds on the probability of decoding error for finite length stabilizer and CSS codes. CSS codes have many advantages for practical applications. Our results show that CSS codes of small lengths, like 100 qubits, visibly lose in performance to generic stabilizer codes.

In this article, we propose a wirelessly powered Internet-of-Things (IoT) system based on the cell-free massive MIMO technology. In such a system, during the downlink phase, the sensors harvest radio-frequency (RF) energy emitted by the distributed access points (APs). During the uplink phase, sensors transmit data to the APs using the harvested energy. Collocated massive MIMO and small-cell IoT can be treated as special cases of cell-free IoT. We derive the tight closed-form lower bound on the amount of harvested energy, and the closed-form expression of SINR as the metrics of power transfer and data transmission, respectively. To improve energy efficiency, we jointly optimize the uplink and downlink power control coefficients to minimize the total transmit energy consumption while meeting the target SINRs. Extended simulation results show that cell-free IoT outperforms collocated massive MIMO and small-cell IoT in terms of both downlink and uplink 95% likely performances. Moreover, significant gains can be achieved by the proposed joint power control in terms of both per user throughput and energy consumption.

This article presents a novel way to reduce blockchain nodes’ memory requirements using error correcting codes. In particular, LDPC codes are taken as examples to explicitly demonstrate the scheme. The proposed coding scheme encodes data across multiple blocks, respectively, block headers, in the blockchain. This leads to a significant reduction in required memory at each node. We then apply the proposed coding technique to blockchains organized in two different ways. Our first scheme has the same protocol for mining, broadcasting, and verification of blocks, as Bitcoin-type blockchains. Our scheme is different in thatfull nodesdo not have to store all blocks. Instead they will need to store only one block of a group of$t$blocks. In the second scheme, we consider a new block verification protocol and an account-based model under the assumption that transmission between any two nodes can be established, as well as the broadcast transmission. Our block verification protocol uses the Byzantine fault tolerance algorithm and requires sending a newly mined block to only a small number of verification nodes, instead of broadcasting it to the entire network, which leads to a reduction of the network load.

Performing active quantum error correction to protect fragile quantum states highly depends on the correctness of measured error syndromes. To obtain reliable error syndromes using imperfect physical circuits, we propose syndrome measurement (SM) and quantum data-syndrome (DS) codes. SM codes protect syndrome with linearly dependent redundant stabilizer measurements. DS codes generalize this idea for simultaneous correction of both data qubits and syndrome bits errors. We study fundamental properties of quantum DS codes, including split weight enumerators, generalized MacWilliams identities, and linear programming bounds. In particular, we derive Singleton and Hamming-type upper bounds on the minimum distance of degenerate quantum DS codes. Then we study random DS codes and show that random DS codes with a relatively small additional syndrome measurements achieve the Gilbert-Varshamov bound of stabilizer codes. Finally, we propose a family of CSS-type quantum DS codes based on classical cyclic codes, which include the Steane code and the quantum Golay code.

A massive MIMO system entails a large number of base station antennas M serving a much smaller number of users. This leads to large gains in spectral and energy efficiency compared with other technologies. As the number of antennas M grows, the performance of such systems gets limited by pilot contamination interference. Large Scale Fading Precoding/Postcoding (LSFP) was proposed for mitigation of pilot contamination, and it was shown that in channels without spatial correlation (uncorrelated base station antennas) LSFP leads to large spectral-efficiency gains. It was recently proven that if a channel has spatial correlation, then one can use this correlation to drastically reduce the pilot contamination interference in the asymptotic regime as M tends to infinity. In this work, we analyze the performance of Uplink (UL) transmission of massive MIMO systems with finitely many antennas M for channels with spatial correlation. We extend the idea of LSFP to correlated channel models and derive SINR expressions that depend only on slow fading channel components for such systems with and without LSFP. These simple expressions lead us to simple algorithms for transmit power optimization. As a result, we obtain a multi-fold increase in data transmission rates.

A wireless massive multiple-input multiple-output (MIMO) system entails a large number of base station antennas serving a much smaller number of users, with large gains in spectral efficiency and energy efficiency compared with the conventional MIMO technology. Until recently, it was believed that as the number of base station antennas tends to infinity, the performance of such systems is limited by directed inter-cellular interference caused by unavoidable re-use of training sequences (pilot contamination) by users in different cells. We devise a new concept of large-scale fading precoding (LSFP) that leads to the effective elimination of inter-cell interference. The main idea of LSFP is that base stations linearly combine messages aimed at users from different cells that re-use the same training sequence. Crucially, the combining coefficients depend only on the large-scale fading coefficients between the users and the base stations. These coefficients change slowly and their number does not depend on the number of base station antennas. Thus, the traffic between base stations stays constant even if the number of antennas tends to infinity. Furthermore, we derive a capacity lower bound for massive MIMO systems with LSFP and a finite number of base station antennas. In this regime, mitigation of all types of interference, not only the pilot contamination, is required. We consider optimal and suboptimal LSFP precodings that take into account all sources of interference. Our simulations results show that LSFP provides significant gain even for the case of moderate number of base station antennas.

We consider a single-cell downlink time-division duplex-based massive MIMO communication in the presence of an adversary capable of jamming and eavesdropping simultaneously. We show that the massive MIMO communication is naturally resilient to no training-phase jamming attack in which the adversary jams only the data communication and eavesdrops both the data communication and the training. Specifically, we show that the secure degrees of freedom (SDoF) attained in the presence of such an attack are identical to the maximum DoF attainable under no attack. Furthermore, we evaluate the number of base station (BS) antennas necessary in order to establish information theoretic security without even a need for Wyner encoding for a given rate of information leakage to the attacker. Next, we show that things are completely different once the adversary starts jamming the training phase. Specifically, we consider the pilot contamination attack, called training-phase jamming in which the adversary jams and eavesdrops both the training and the data communication. We show that under such an attack, the maximum achieved SDoF is identical to zero. Furthermore, the maximum achievable secure rates of users also vanish, even in the asymptotic regime in the number of the BS antennas. We finally address this attack and show that, under training-phase jamming, if the number of pilot signals is scaled in a certain way and the pilot signal assignments can be hidden from the adversary, the users achieve an SDoF identical to the maximum achievable DoF under no attack.

Linear programming approaches have been applied to derive upper bounds on the size of classical and quantum codes. In this paper, we derive similar results for general quantum codes with entanglement assistance by considering a type of split weight enumerator. After deriving the MacWilliams identities for these enumerators, we are able to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. Our Singleton bound and Hamming bound are more general than the previous bounds for entanglement-assisted quantum stabilizer codes. In addition, we show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large. On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve the linear programming bounds on the minimum distance of quantum codes of small length. In particular, we show that there is no [[27, 15, 5]] or [[28, 14, 6]] stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement quantum stabilizer codes with length up to 20 are significantly improved.

In this paper, we define two split weight enumerators for general quantum codes with entanglement assistance, including nonadditive codes. We show that they obey a MacWilliams identity, which allows us to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. On the other hand, we derive additional constraints on the size of Pauli subgroups for quantum codes, which helps to improve the linear programming bounds on the minimum distance of quantum codes of small length.

A massive MIMO system entails a large number (tens or hundreds) of base station antennas serving a much smaller number of terminals. These systems demonstrate large gains in spectral and energy efficiency compared with the conventional MIMO technology. As the number of antennas grows, the performance of a massive MIMO system gets limited by the interference caused by pilot contamination. Ashikhmin and Marzetta proposed (under the name of Pilot Contamination Precoding) large scale fading precoding (LSFP) and large scale fading decoding (LSFD) based on limited cooperation between base stations. They showed that zero-forcing LSFP and LSFD eliminate pilot contamination entirely and lead to an infinite throughput as the number of antennas grows. In this paper, we focus on the uplink and show that even in the case of a finite number of base station antennas, LSFD yields a very large performance gain. In particular, one of our algorithms gives a more than 140 fold increase in the 5% outage data transmission rate! We show that the performance can be improved further by optimizing the transmission powers of the users. Finally, we present decentralized LSFD that requires limited cooperation only between neighboring cells.

Cell-free Massive multiple-input multiple-output (MIMO) comprises a large number of distributed low-cost low-power single antenna access points (APs) connected to a network controller. The number of AP antennas is significantly larger than the number of users. The system is not partitioned into cells and each user is served by all APs simultaneously. The simplest linear precoding schemes are conjugate beamforming and zero-forcing. Max-min power control provides equal throughput to all users and is considered in this paper. Surprisingly, under max-min power control, most APs are found to transmit at less than full power. The zero-forcing precoder significantly outperforms conjugate beamforming. For zero-forcing, a near-optimal power control algorithm is developed that is considerably simpler than exact max-min power control. An alternative to cell-free systems is small-cell operation in which each user is served by only one AP for which power optimization algorithms are also developed. Cell-free Massive MIMO is shown to provide five- to ten-fold improvement in 95%-likely per-user throughput over small-cell operation.

A Cell-Free Massive MIMO (multiple-input multiple-output) system comprises a very large number of distributed access points (APs), which simultaneously serve a much smaller number of users over the same time/frequency resources based on directly measured channel characteristics. The APs and users have only one antenna each. The APs acquire channel state information through time-division duplex operation and the reception of uplink pilot signals transmitted by the users. The APs perform multiplexing/de-multiplexing through conjugate beamforming on the downlink and matched filtering on the uplink. Closed-form expressions for individual user uplink and downlink throughputs lead to max-min power control algorithms. Max-min power control ensures uniformly good service throughout the area of coverage. A pilot assignment algorithm helps to mitigate the effects of pilot contamination, but power control is far more important in that regard. Cell-Free Massive MIMO has considerably improved performance with respect to a conventional small-cell scheme, whereby each user is served by a dedicated AP, in terms of both 95%-likely per-user throughput and immunity to shadow fading spatial correlation. Under uncorrelated shadow fading conditions, the cell-free scheme provides nearly fivefold improvement in 95%-likely per-user throughput over the small-cell scheme, and tenfold improvement when shadow fading is correlated.

Performing active quantum error correction to protect fragile quantum states highly depends on the correctness of error information-error syndromes. To obtain reliable error syndromes using imperfect physical circuits, we propose the idea of quantum data-syndrome (DS) codes that are capable of correcting both data qubits and syndrome bits errors. We study fundamental properties of quantum DS codes and provide several CSS-type code constructions of quantum DS codes.

A Large Scale Antenna System (LSAS) entails a large number (tens or hundreds) of base station antennas serving a much smaller number of terminals, with large gains in spectral-efficiency and energy efficiency compared with conventional MIMO technology. As the number of antennas grows, the performance of an LSAS gets limited by pilot contamination, arising due to the use of same pilot sequences for channel estimation in neighboring cells. Recently A. Ashikhmin and T. Marzetta showed that using proper precoding/postcoding (PCP) and limited cooperation between cells, it is possible to eliminate pilot contamination entirely and get infinite throughput as M → ∞. In this paper, we focus on the uplink of an LSAS and show that even in the case of a finite number of base station antennas, PCP yields very significant performance gain in terms of data transmission rates. In particular, one of our algorithms gives a 140 fold increase in the 5% outage data transmission rates! We also show that the performance can be improved further by optimizing the transmission powers of the users, and present a simple decentralized algorithm in order to solve it.

An important issue in the implementation of a quantum computer is to protect quantum information from decoherence. In fault-tolerant quantum computation, the circuits used to measure the error syndromes are themselves faulty; to minimize the effect of syndrome measurement errors, the syndromes are measured repeatedly. This paper introduces a scheme based on classical codes to make this process more robust and/or reduce the needed resources and measurement time. We analyze particular implementations based on low-density generator matrix (LDGM) codes using EXIT functions.

In this paper, we estimate the fidelity of stabilizer and CSS codes. First, we derive a lower bound on the fidelity of a stabilizer code via its quantum enumerator. Next, we find the average quantum enumerators of the ensembles of finite length stabilizer and CSS codes. We use the average quantum enumerators for obtaining lower bounds on the average fidelity of these ensembles. We further improve the fidelity bounds by estimating the quantum enumerators of expurgated ensembles of stabilizer and CSS codes. Finally, we derive fidelity bounds in the asymptotic regime when the code length tends to infinity. These results tell us which code rate we can afford for achieving a target fidelity with codes of a given length. The results also show that in symmetric depolarizing channel a typical stabilizer code has better performance, in terms of fidelity and code rate, compared with a typical CSS codes, and that balanced CSS codes significantly outperform other CSS codes. Asymptotic results demonstrate that CSS codes have a fundamental performance loss compared with stabilizer codes.

In this paper we study the performance of cellular networks when their base stations have an unlimited number of antennas. In previous work, the asymptotic behavior of the signal to interference plus nose ratio (SINR) was obtained. We revisit these results by deriving the rigorous expression for the SINR of both downlink and uplink in the scenario of infinite number of antennas. We show that the contamination of the channel estimates happens whenever a pilot sequence is received at a base station simultaneously with non-orthogonal signals coming from other users. We propose a method to avoid such simultaneous transmissions from adjacent cells, thus significantly decreasing interference. We also investigate the effects of power allocation in this interference-limited scenario, and show that it results in gains of over 15dB in the signal to interference ratio for the scenario simulated here. The combination of these two techniques results in rate gains of about 18 times in our simulations.

An LSAS entails a large number (tens or hundreds) of base station antennas serving a much smaller number of terminals, with large gains in spectral-efficiency and energy-efficiency compared with conventional MIMO technology. Until recently it was believed that in multi-cellular LSAS, even in the asymptotic regime, as the number of service antennas tends to infinity, the performance is limited by directed inter-cellular interference. The interference results from unavoidable re-use of reverse-link pilot sequences (pilot contamination) by terminals in different cells. We devise a new concept that leads to the effective elimination of inter-cell interference in TDD LSAS systems. This is achieved by outer multi-cellular pre-coding, which we call pilot contamination pre-coding (PCP). The main idea of PCP is that each base station linearly combines messages aimed to terminals from different cells that re-use the same pilot sequence. Crucially, the combining coefficients depend only on the slow-fading coefficients between the terminals and the base stations. Each base station independently transmits its PCP-combined symbols using conventional linear pre-coding that is based on estimated fast-fading coefficients. Further we derive estimates for SINRs and a capacity lower bound for the case of LSASs with PCP and finite number of antennas M.

This paper considers a multi-cell multiple antenna system with precoding used at the base stations for downlink transmission. Channel state information (CSI) is essential for precoding at the base stations. An effective technique for obtaining this CSI is time-division duplex (TDD) operation where uplink training in conjunction with reciprocity simultaneously provides the base stations with downlink as well as uplink channel estimates. This paper mathematically characterizes the impact that uplink training has on the performance of such multi-cell multiple antenna systems. When non-orthogonal training sequences are used for uplink training, the paper shows that the precoding matrix used by the base station in one cell becomes corrupted by the channel between that base station and the users in other cells in an undesirable manner. This paper analyzes this fundamental problem of pilot contamination in multi-cell systems. Furthermore, it develops a new multi-cell MMSE-based precoding method that mitigates this problem. In addition to being linear, this precoding method has a simple closed-form expression that results from an intuitive optimization. Numerical results show significant performance gains compared to certain popular single-cell precoding methods.

This paper considers the problem of interference mitigation in multi-cell multi-antenna time division duplex (TDD) wireless systems for downlink transmission. An efficient way to obtain channel state information (CSI) at the base station is by using uplink pilots and reciprocity of the downlink channel. At the same time, it has been shown that pilots from different cells contaminate each other, resulting in corruption of precoding matrices used by base stations, and high inter-cell interference. This paper studies the effects of shifting the location of pilots in time frames used in neighboring cells, and its effectiveness in obtaining better channel estimates, and, thereby, inter-cell interference reduction.

This paper examines near capacity performance of Markov Chain Monte Carlo (MCMC) detectors for multiple-input and multiple-output (MIMO) channels. The proposed MCMC detector (Log-MAP-tb b-MCMC) operates in a strictly bit-wise fashion and adopts Log-MAP algorithm with table look-up. When concatenated with an optimized low-density parity-check (LDPC) code, Log-MAP-tb b-MCMC can operate within 1.2-1.8 dB of the capacity of MIMO systems with 8 transmit/receive antennas at spectral efficiencies up to ¿ = 24 bits/channel use (b/ch). This result improves upon best performance achieved by turbo coded systems using list sphere decoding (LSD) detector by 2.3-3.8 dB, leading to nearly 50% reduction in the capacity gap. Detailed comparisons of the Log-MAP-tb b-MCMC with LSD based detectors demonstrate that MCMC detector is indeed the detector of choice for achieving channel capacity both in terms of performance and complexity.

This paper introduces multidimensional generalizations of binary Reed-Muller codes where the codewords are projection operators, and the corresponding subspaces are widely separated with respect to the chordal distance on Grassmannian space. Parameters of these Grassmannian packings are derived and a low complexity decoding algorithm is developed by modifying standard decoding algorithms for binary Reed-Muller codes. The subspaces are associated with projection operators determined by Pauli matrices appearing in the theory of quantum error correction and this connection with quantum stabilizer codes may be of independent interest. The Grassmannian packings constructed here find application in noncoherent wireless communication with multiple antennas, where separation with respect to the chordal distance on Grassmannian space guarantees closeness to the channel capacity. It is shown that the capacity of the noncoherent multiple-input-multiple-output (MIMO) channel at both low and moderate signal-to-noise ratio (SNR) (under the constraint that only isotropically distributed unitary matrices are used for information transmission) is closely approximated by these packings.

This paper considers a multi-cell multiple antenna system with precoding at the base stations for downlink transmission. To enable precoding, channel state information (CSI) is obtained via uplink training. This paper mathematically characterizes the impact that uplink training has on the performance of multi-cell multiple antenna systems. When non-orthogonal training sequences are used for uplink training, it is shown that the precoding matrix used by the base station in one cell becomes corrupted by the channel between that base station and the users in other cells. This problem of pilot contamination is analyzed in this paper. A multi-cell MMSE-based precoding is proposed that, when combined with frequency/time/pilot reuse techniques, mitigate this problem.

Rapid acquisition of accurate crosstalk estimates is a core requirement for effective preceding in digital subscriber line (DSL) systems. It is shown that signal-to-noise ratio (SNR) reports provided by customer premises equipment (CPE) can be used to perform this task by "tuning" the precoder, i.e., iterating alternate steps of estimation and precoder adaptation. Such an approach has the advantage that it can be applied to legacy CPEs. Estimation algorithms are designed using techniques from stochastic control.

The downlink transmission in multi-user multiple- input multiple-output (MIMO) systems has been extensively studied from both communication-theoretic and information-theoretic perspectives. Most of these papers assume perfect/imperfect channel knowledge. In general, the problem of channel estimation is studied separately. However, in interference-limited communication systems with high mobility, the problem of channel estimation is tightly coupled with the problem of maximizing throughput of the system. In this paper, scheduling and preconditioning in the presence of reciprocal time-division duplex (TDD) training are considered. In the case of homogeneous users, a scheduling scheme is proposed and an improved lower bound on the sum capacity is derived. The problem of choosing training sequence length to maximize net throughput of the system is also studied. In the case of heterogeneous users, a modified pre-conditioning method is proposed and an optimized pre-conditioning matrix is derived. This method is combined with a scheduling scheme to further improve achievable weighted-sum rate.

In this paper, we design capacity approaching low- density parity-check (LDPC) codes in the low signal-to-noise ratio (SNR) regime for flat Rayleigh fading channels with channel side information at transmitter and receiver. We use the structure advocated by Caire et al, which uses a single codebook with dynamic power allocation. The extrinsic information transfer (EXIT) function method is used to design the LDPC codes which approach the channel capacities. We also study the EXIT function properties of various demappers.

We study an improved receiver with iterative channel estimation and decoding for wireless multipath channels with RAKE reception. To keep the complexity low, iterative channel estimation is done on the equivalent channel at the RAKE output. Output after Turbo decoding iteration(s) is processed to yield a better channel estimate.

In this paper, we study moments of soft bits of binary-input symmetric-output channels and solve some extremal problems of the moments. We use these results to solve the extremal information combining problem. Further, we extend the information combining problem by adding a constraint on the second moment of soft bits, and find the extremal distributions for this new problem. The results for this extension problem are used to improve the prediction of convergence of the belief propagation decoding of low-density parity-check (LDPC) codes, provided that another extremal problem related to the variable nodes is solved.

The extrinsic information transfer (EXIT) functions of Hadamard codes in the context of repeat-zigzag-Hadamard (RZH) codes with parallel decoding are investigated. EXIT functions over both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise (BIAWGN) channel are derived. The application of these EXIT functions in the design of low-rate capacity-approaching irregular RZH (IRZH) codes is also considered. Using the EXIT functions, the bit error rate (BER) for a given code profile can be easily estimated and the differential evolution (DE) technique can be employed to find the optimal degree profile for given design parameters. The EXIT functions derived in this communication can serve as an effective tool for designing low-rate IRZH codes with parallel decoding in both BEC and BIAWGN channels.

To apply the promising idea of iterative information processing to the problem of joint channel estimation and data decoding, one may utilize the soft information of the coded bits to help refine the channel estimate, e.g., with Wiener filtering. However, the performance of such an iterative approach depends on not only the construction of the iteratively refined soft channel, but also the structure of the adopted error-correction code. Through extrinsic information transfer chart analysis, we investigate the impact of different soft channel construction schemes on multicarrier systems possessing turbo coding/modulation structures: (1) one with bit-interleaved coded modulation signals, and (2) the other with low-density parity- check code encoded modulation signals. It is shown that the former benefits significantly from iterative information processing regardless of channel construction scheme and the performance of the systems with different schemes converges. On the contrary, the same observation cannot be applied to the latter, a capacity- approaching system.

It is well known that availability of the channel state information (CSI) at the transmitter significantly increases the throughput of MIMO broadcast systems. For even larger increase of the throughput it is important to identify and to transmit to receivers whose channel vectors are almost orthogonal to each other. Since typically the feedback link from the receivers to the transmitter is low-rate, only a quantized version of the CSI can be sent back to the transmitter. In this paper we consider the problem of designing Grassmannian packings that can serve as good quantization codebooks, have low maximum likelihood decoding complexity, and allow to identify receivers with orthogonal, and/or almost orthogonal, channel vectors in a very efficient way.

We investigate the extrinsic information transfer (EXIT) functions of Hadamard codes in the context of repeat- zigzag Hadamard (RZH) codes with parallel decoding. The derived EXIT functions can serve as an effective tool for designing low-rate IRZH codes with parallel decoding in BIAWGN channels.

We derive a generalization of a result in representation theory. Using this generalization, we construct new families of Grassmannian packings associated with binary Reed-Muller codes and we develop a low complexity decoding algorithm by modifying standard decoding algorithms for these binary codes. The subspaces are associated with projection operators which arise in the theory of quantum stabilizer codes. These Grassmannian packings find application as highly structured examples of dictionaries that admit fast algorithms for identifying sparse representations, and in noncoherent wireless communication with multiple antennas. The capacity of the noncoherent MIMO channel at both low and moderate SNR (under the constraint that only isotropically distributed unitary matrices are used for information transmission) is closely approximated by these packings

We consider a generalization of a classical ARQ protocol for the case of quantum error correcting codes and the quantum depolarizing channel. We define the fidelity of the ARQ protocol as the probability that the outcome of a measurement of the received quantum state is collinear to the transmitted quantum state, under the condition that the measurement outcome belongs to the code space. Further, we derive tight upper and lower bounds on the exponent of the fidelity of the ARQ protocol. The obtained bounds show a threshold behavior of the fidelity. Namely, in asymptotics, as the code length tends to infinity, the fidelity tends to either 1 or 0 depending on the code rate and the probability of error of the quantum depolarizing channel.

Use of extrinsic information transfer (EXIT) functions, characterizing the amplification of mutual information between the input and output of the maximum a posteriori (MAP) decoder, significantly facilitates analysis of iterative coding schemes. Previously, EXIT functions derived for binary erasure channels (BECs) were used as an approximation for other channels. Here, we improve on this approach by introducing more accurate methods to construct EXIT functions for binary-input memoryless symmetric (BMS) channels. By defining an alternative pseudo-MAP decoder coinciding with the MAP decoder over BEC, we provide an expression for the EXIT functions of block codes over BEC. Furthermore, we draw a connection between the EXIT function over BEC and the EXIT function over the BMS channel under certain conditions. This is used for deriving accurate or approximate expressions of EXIT functions over BMS channels in certain scenarios

We exploit extrinsic information tranfer functions of single parity-check and prepetition codes over the binay input additive white Gaussian noise (biAWGN) channel, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that our method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods.

We exploit extrinsic information transfer functions of single parity-check and repetition codes over the binary input additive white Gaussian noise (biAWGN) channel, derived by the authors, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that this method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding error probability. Specifically, it is assumed that there exists a family of codes of length N and rate R=(1-epsiv)C (C is a capacity of a binary-symmetric channel), whose decoding probability decreases inverse polynomially in N. It is shown that if the decoding probability decreases sufficiently fast, but still only inverse polynomially fast in N, then there exists another such family of codes whose decoding error probability decreases exponentially fast in N. Moreover, if the decoding time complexity of the assumed family of codes is polynomial in N and 1/epsiv, then the decoding time complexity of the presented family is linear in N and polynomial in 1/epsiv. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes", IEEE Transactions on Information Theory, 2002, and "Concatenated Codes: Serial and Parallel", IEEE Transactions on Information Theory, 2005. It is shown that the latter families cannot be tuned to have exponentially decaying (in N) error probability, and at the same time to have decoding time complexity linear in N and polynomial in 1/epsiv

We present a family of space-time codes for the noncoherent MIMO channel. The codes are constructed via functions that can be considered as a generalization of boolean functions to commuting projection operators which arise in the theory of quantum stabilizer codes. These space-time codes are strongly related to standard binary Reed-Muller codes. In particular, they can be decoded by adapting a decoding algorithm for Reed-Muller codes. We show that the first subclass of codes from this family, which we view as the first order space-time Reed-Muller codes, allow transmission with rates close to the MIMO noncoherent channel capacity in the low signal to noise ratio (SNR) regime

The concatenation of nearly-MDS expander codes of Roth and Skachek, "On Nearly-MDS Expander Codes," Proc. IEEE ISIT'04, with 'typical' LDPC codes is investigated. It is shown that for the rates R = (1 - epsi)C (C is the capacity of the binary symmetric channel (BSC)), under certain condition on the parameters of LDPC codes, these concatenated codes have decoding time linear in their length and polynomial in 1/epsi, and the decoding error probability decays exponentially. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes," IEEE Trans. Inform. Theory, 2002, and "Concatenated Codes: Serial and Parallel," IEEE Trans. Inform. Theory, 2005. It is shown that the latter families can not be tuned to have all the aforementioned properties

In this paper we study moments of soft-bits of binary-input symmetric-output channels and solve some extremal problems of the moments. We use these results to solve the extremal information combining problem. Further, we extend the information combining problem by adding a constraint on the second moment of soft-bits, and find the extreme distributions for this new problem

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis, we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg, and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

Use of extrinsic information transfer (EXIT) functions characterizing mutual information between the input and output of constituent decoders significantly facilitates performance analysis of iterative decoding schemes. Previously EXIT functions derived for binary erasure channel (BEC) were used as an approximation for other binary memoryless symmetric (BMS) Channels. Here we improve on this approach by introducing a more accurate method to compute EXIT functions of some block codes for BMS channels. A general expression is derived for the extrinsic mutual information at the output of MAP decoder. Using this expression we are able to compute EXIT functions for single parity-check codes over all BMS channels. Application of this result to analysis of convergence thresholds of LDPC codes is described. Using an alternative decoder coinciding with MAP decoder over BEC, we derive an expression for EXIT function over BEC, and based on it approximation to the EXIT function over AWGN channel for some block codes.

A coding and modulation technique is studied where the coded bits of an irregular low-density parity-check (LDPC) code are passed directly to a modulator. At the receiver, the variable nodes of the LDPC decoder graph are connected to detector nodes, and iterative decoding is accomplished by viewing the variable and detector nodes as one decoder. The code is optimized by performing a curve fitting on extrinsic information transfer charts. Design examples are given for additive white Gaussian noise channels, as well as multiple-input, multiple-output (MIMO) fading channels where the receiver, but not the transmitter, knows the channel. For the MIMO channels, the technique operates within 1.25 dB of capacity for various antenna configurations, and thereby outperforms a scheme employing a parallel concatenated (turbo) code by wide margins when there are more transmit than receive antennas.

Extrinsic information transfer (EXIT) charts are a tool for predicting the convergence behavior of iterative processors for a variety of communication problems. A model is introduced that applies to decoding problems, including the iterative decoding of parallel concatenated (turbo) codes, serially concatenated codes, low-density parity-check (LDPC) codes, and repeat-accumulate (RA) codes. EXIT functions are defined using the model, and several properties of such functions are proved for erasure channels. One property expresses the area under an EXIT function in terms of a conditional entropy. A useful consequence of this result is that the design of capacity-approaching codes reduces to a curve-fitting problem for all the aforementioned codes. A second property relates the EXIT function of a code to its Helleseth-Klove-Levenshtein information functions, and thereby to the support weights of its subcodes. The relation is via a refinement of information functions called split information functions, and via a refinement of support weights called split support weights. Split information functions are used to prove a third property that relates the EXIT function of a linear code to the EXIT function of its dual.

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.

We present new MAP decoding algorithms for first order Reed-Muller and Hamming codes. The proposed algorithms have complexities proportional to n/spl times/log/sub 2/(n), where n is the code length.

We consider the problem of bounding the distance distribution for unrestricted block codes with known distance and/or dual distance. Applying the polynomial method, we provide a general framework for previously known results. We derive several upper and lower bounds both for finite length and for sequences of codes of growing length. Asymptotic results in the paper improve previously known estimates. In particular, we prove the best known bounds on the binomiality range of the distance spectrum of codes with a known dual distance.

We define and show how to construct nonbinary quantum stabilizer codes. Our approach is based on nonbinary error bases. It generalizes the relationship between self-orthogonal codes over F/sub 4/ and binary quantum codes to one between self-orthogonal codes over F(q/sup 2/) and q-ary quantum codes for any prime power q.

This paper is devoted to the problem of error detection with quantum codes. We show that it is possible to give a consistent definition of the undetected error event. To prove this, we examine possible problem settings for quantum error detection. Our goal is to derive a functional that describes the probability of undetected error under natural physical assumptions concerning transmission with error detection with quantum codes. We discuss possible transmission protocols with stabilizer and unrestricted quantum codes. The set of results proved in the paper shows that in all the cases considered the average probability of undetected error for a given code is essentially given by one and the same function of its weight enumerators. We examine polynomial invariants of quantum codes and show that coefficients of Rains's (see ibid., vol44, p.1388-94, 1998) "unitary weight enumerators" are known for classical codes under the name of binomial moments of the distance distribution. As in the classical situation, these enumerators provide an alternative expression for the probability of undetected error.

In Part I of this paper we formulated the problem of error detection with quantum codes on the completely depolarized channel and gave an expression for the probability of undetected error via the weight enumerators of the code.In this part we show that there exist quantum codes whose probability of undetected error falls exponentially with the length of the code and derive bounds on this exponent.The lower (existence) bound is proved for stabilizer codes by the counting argument for classical self-orthogonal quaternary codes.Upper bounds are proved by linear programming.First we formulate two linear programming problems that are convenient for the analysis of specific short codes.Next we give a relaxed formulation of the problem in terms of optimization on the cone of polynomials in the Krawtchouk basis.We present two general solutions of the problem.Together they give an upper bound on the exponent of undetected error.The upper and lower asymptotic bounds coincide for a certain interval of code rates close to 1.

We derive a new upper bound on the exponent of error probability of decoding for the best possible codes in the Gaussian channel. This bound is tighter than the known upper bounds (the sphere-packing and minimum-distance bounds proved in Shannon's classical 1959 paper and their low-rate improvement by Kabatiansky and Levenshtein (1978)). The proof is accomplished by studying asymptotic properties of codes on the sphere S/sup n-1/(R). First we prove a general lower bound on the distance distribution of codes of large size. To derive specific estimates of the distance distribution, we study the asymptotic behavior of Jacobi polynomials P/sub k//sup ak, bk/ as k/spl rarr//spl infin/. Since on the average there are many code vectors in the vicinity of the transmitted vector x, one can show that the probability of confusing x and one of these vectors cannot be too small. This proves a lower bound on the error probability of decoding and the upper bound announced in the title.

We study a combinatorial invariant of codes which counts the number of ordered pairs of codewords in all subcodes of restricted support in a code. This invariant can be expressed as a linear form of the components of the distance distribution of the code with binomial numbers as coefficients. For this reason we call it a binomial moment of the distance distribution. Binomial moments appear in the proof of the MacWilliams (1963) identities and in many other problems of combinatorial coding theory. We introduce a linear programming problem for bounding these linear forms from below. It turns out that some known codes (1-error-correcting perfect codes, Golay codes, Nordstrom-Robinson code, etc.) yield optimal solutions of this problem, i.e., have minimal possible binomial moments of the distance distribution. We derive several general feasible solutions of this problem, which give lower bounds on the binomial moments of codes with given parameters, and derive the corresponding asymptotic bounds. Applications of these bounds include new lower bounds on the probability of undetected error for binary codes used over the binary-symmetric channel with crossover probability p and optimality of many codes for error detection. Asymptotic analysis of the bounds enables us to extend the range of code rates in which the upper bound on the undetected error exponent is tight.

We derive new asymptotic upper bounds on the generalized weights of a binary linear code of a given size. We also prove some asymptotic results on the distance distribution of binary codes.

The covering radius of a code tells us how far in the sense of Hamming distance an arbitrary word of the ambient space can be from the code. For a few decades this parameter has been widely studied. We estimate the covering ratios of a code when the dual distance is known. We derive a new bound on covering radii of linear codes. It improves essentially on the previously known estimates in a certain wide range. We also study asymptotic bounds on the cardinality of constant weight codes.

This paper is concerned with bounds for quantum error-correcting codes. Using the quantum MacWilliams (1972, 1977) identities, we generalize the linear programming approach from classical coding theory to the quantum case. Using this approach, we obtain Singleton-type, Hamming-type, and the first linear-programming-type bounds for quantum codes. Using the special structure of linear quantum codes, we derive an upper bound that is better than both Hamming and the first linear programming bounds on some subinterval of rates.

Minimal vectors in linear codes arise in numerous applications, particularly, in constructing decoding algorithms and studying linear secret sharing schemes. However, properties and structure of minimal vectors have been largely unknown. We prove basic properties of minimal vectors in general linear codes. Then we characterize minimal vectors of a given weight and compute their number in several classes of codes, including the Hamming codes and second-order Reed-Muller codes. Further, we extend the concept of minimal vectors to codes over rings and compute them for several examples. Turning to applications, we introduce a general gradient-like decoding algorithm of which minimal-vectors decoding is an example. The complexity of minimal-vectors decoding for long codes is determined by the size of the set of minimal vectors. Therefore, we compute this size for long randomly chosen codes. Another example of algorithms in this class is given by zero-neighbors decoding. We discuss relations between the two decoding methods. In particular, we show that for even codes the set of zero neighbors is strictly optimal in this class of algorithms. This also implies that general asymptotic improvements of the zero-neighbors algorithm in the frame of gradient-like approach are impossible. We also discuss a link to secret-sharing schemes.