Naoko KIFUNE Hironori UCHIKAWA
At a flash memory, each stored data frame is protected by error correction codes (ECC) such as Bose-Chaudhuri-Hocquenghem (BCH) codes from random errors. Exclusive-OR (XOR) based erasure codes like RAID-5 have also been employed at the flash memory to protect from memory block defects. Conventionally, the ECC and erasure codes are used separately since their target errors are different. Due to recent aggressive technology scaling, additional error correction capability for random errors is required without adding redundancy. We propose an algorithm to improve error correction capability by using XOR parity with a simple counter that counts the number of unreliable bits in the XOR stripe. We also propose to apply Chase decoding to the proposed algorithm. The counter makes it possible to reduce the false correction and execute the efficient Chase decoding. We show that combining the proposed algorithm with Chase decoding can significantly improve the decoding performance.
Computing the weight distribution of a code is a challenging problem in coding theory. In this paper, the weight distributions of (256, k) extended binary primitive BCH codes with k≤71 and k≥187 are given. The weight distributions of the codes with k≤63 and k≥207 have already been obtained in our previous work. Affine permutation and trellis structure are used to reduce the computing time. Computer programs in C language which use recent CPU instructions, such as SIMD, are developed. These programs can be deployed even on an entry model workstation to obtain the new results in this paper.
The Galois hull of linear code is defined to be the intersection of the code and its Galois dual. In this paper, we investigate the Galois hulls of cyclic codes over Fqr. For any integer s≤r, we present some sufficient and necessary conditions that cyclic codes have l-dimensional s-Galois hull. Moreover, we prove that a cyclic code C has l-dimensional s-Galois hull iff C has l-dimensional (r-s)-Galois hull. In particular, we also present the sufficient and necessary condition for cyclic codes with 1-dimensional Galois hulls and the relationship between cyclic codes with 1-dimensional Galois hulls and cyclic codes with Galois complementary duals. Some optimal cyclic codes with Galois hulls are obtained. Finally, we explicitly construct a class of cyclic codes with 1-Galois linear complementary dual over Fq3.
Nianqi TANG Zhuo LI Lijuan XING Ming ZHANG Feifei ZHAO
Maximal designed distances for nonbinary narrow-sense quantum Bose-Chaudhuri-Hocquenghem (BCH) codes of length $n=rac{q^4-1}{r}$ and new constructions for them are given, where q is an odd prime power. These constructions are capable of designing quantum BCH codes with new parameters. Furthermore, some codes obtained here have better parameters than those constructed by other known constructions.
Yingjing QIAN Ni ZHOU Dajiang HE
Device-to-device (D2D) communication enables two local users to communicate with each other directly instead of relaying through a third party, e.g., base station. In this paper, we study a subchannel sharing strategy underlaying multichannel cellular network for D2D pairs and existing cellular users (CUs). In the investigated scenario, we try to improve the spectrum efficiency of D2D pairs, but inevitably brings cross interference between two user groups. To combat interference, we attempt to assign each D2D pair with appropriate subchannels, which may belong to different CUs, and manipulate transmission power of all users so as to maximize the sum rate of all D2D pairs, while assuring each CU with a minimum data rate on its subchannel set. The formulated problem is a nonconvex problem and thus, obtaining its optimal solution is a tough task. However, we can find optimal power and subchannel assignment for a special case by setting an independent data rate constraint on each subchannel. Then we find an efficient method to calculate a gradient for our original problem. Finally, we propose a gradient-based search method to address the problem with coupled minimum data rate constraint. The performance of our proposed subchannel sharing strategy is illustrated via extensive simulation results.
Makoto TAKITA Masanori HIROTOMO Masakatu MORII
In this paper, we discuss an algebraic decoding of BCH codes over symbol-pair read channels. The channels output overlapping pairs of symbols in storage applications. The pair distance and pair error are used in the channels. We define a polynomial that represents the positions of the pair errors as the error-locator polynomials and a polynomial that represents the positions of the pairs of a received pair vector in conflict as conflict-locator polynomial. In this paper, we propose algebraic methods for correcting two-pair and three-pair errors for BCH codes. First, we show the relation between the error-locator polynomials and the conflict-locator polynomial. Second, we show the relation among these polynomials and the syndromes. Finally, we provide how to correct the pair errors by solving equations including the relational expression by algebraic methods.
Seung-Youl KIM Kyoung-Rok CHO Je-Hoon LEE
This paper presents a new parallel architecture of syndrome generator for a high-speed BCH (Bose-Chaudhuri-Hocquenghem) decoder. In particular, the proposed parallel syndrome generators are based on LFSR (linear feedback shift register) architecture to achieve high throughput without significant area overhead. From the experimental results, the proposed approach achieves 4.60 Gbps using 0.25-µm standard CMOS technology. This result is much faster than the conventional byte-wise GFM-based counterpart. The high throughputs are due to the well-tuned hardware implementation using unfolding transformation.
Jianzhang CHEN Jianping LI Yuanyuan HUANG
Nonprimitive non-narrow-sense BCH codes have been studied by many scholars. In this paper, we utilize nonprimitive non-narrow-sense BCH codes to construct a family of asymmetric quantum codes and two families of quantum convolutional codes. Most quantum codes constructed in this paper are different from the ones in the literature. Moreover, some quantum codes constructed in this paper have good parameters compared with the ones in the literature.
Harumi MURATA Akio OGIHARA Masaki UESAKA
Yajima et al. proposed a method based on amplitude and phase coding of audio signals. This method has relatively high sound quality because human auditory property is considered for embedding. However, in this method, the tolerance to attacks tends to be weak. Hence, we propose a high-tolerance watermarking method using BCH code which is one of error correcting code. This paper evaluates whether our method preserves the sound quality while ensuring high tolerance.
Qi JIANG Xuewen LIAO Wei WANG Shihua ZHU
In this paper, we study the problem of joint resource allocation in the two-way relay system, where a pair of multi-antenna users wish to exchange information via multi-antenna amplify-and-forward relay under orthogonal frequency-division multiplexing (OFDM) modulation. We formulate a sum-rate maximization problem subject to a limited power constraint for each user and relay. Our resource allocation strategy aims at finding the best pairing scheme and optimal power allocation over subchannels in frequency and space domains. This turns out to be a mixed integer programming problem. We then derive an asymptotically optimal solution though the Lagrange dual decomposition approach. Finally, simulation results are provided to demonstrate the performance gain of the proposed algorithms.
Hui DENG Xiaoming TAO Youzheng WANG Jianhua LU
Efficient resource allocation for delay-sensitive traffic, such as telephony and video streaming, in Orthogonal Frequency Division Multiple Access (OFDMA) networks is needed to increase system performance. In our system, users try to achieve a low queuing delay and buffer space usage by competing for transmission over the subchannels. We formulate this problem as a bargaining game and use the Nash Bargaining Solution (NBS) to realize a fair and efficient subchannel allocation for the users. Simulation results show performance improvements, with regard to packet dropping and delay distribution, over other algorithms.
Gye-Tae GIL Seong-Choon LEE Dong-Hoi KIM
This paper presents a novel dynamic subchannel allocation scheme that can improve the cell capacity by coordinating the intercell interference (ICI) in a cellular orthogonal frequency division multiple access (OFDMA) system. The proposed scheme mitigates the ICI by adopting the virtual cell concept and improves the frequency reuse factor through subchannel reuse among different virtual cells. In particular, each virtual cell is assigned a primary and a secondary subchannel group, and each sector base station (BSs) allocates the subchannel resulting in the least ICI in probability out of the candidate subchannels to the mobile stations, dynamically searching from its primary group and then secondary group. In addition, an optional use of pico-cell overlay at the intersection of the virtual cells is also proposed to enhance the fairness of the proposed scheme with the BS-MS distance. Through computer simulation, it is shown that the proposed scheme has the advantages of improved cell capacity and fairness compared to the conventional schemes.
The BCH code is one of the well-known error correction codes and its decoding contains many operations in Galois field. These operations require many instruction steps or large memory area for look-up tables on ordinary processors. While dedicated hardware BCH decoders achieves higher decoding speed than software, the advantage of software decoding is its flexibility to decode BCH codes of variable parameters. In this paper, an auxiliary circuit to be embedded in a pipelined processor is proposed which accelerates software decoding of various BCH codes.
Jae Cheol PARK Yun Hee KIM Een Kee HONG Iickho SONG
Based on game theory, a distributed power control algorithm with sequential subchannel nulling is proposed for ad-hoc networks. It is shown that the proposed method, by sharing subchannels appropriately according to the interference profiles, can reduce the power consumption of the network while satisfying the target rate of each link.
Sangho YOON Hanho LEE Kihoon LEE
This paper presents a high-speed Forward Error Correction (FEC) architecture based on concatenated Bose-Chaudhuri-Hocquenghem (BCH) for 100-Gb/s optical communication systems. The concatenated BCH code consists of BCH(3860, 3824) and BCH(2040, 1930), which provides 7.98 dB net coding gain at 10-12 corrected bit error rate. The proposed BCH decoder features a low-complexity key equation solver using an error-locator computation RiBM (ECRiBM) algorithm and its architecture. The proposed concatenated BCH-based Super-FEC architecture has been implemented in 90-nm CMOS standard cell technology with a supply voltage of 1.1 V. The implementation results show that the proposed architecture can operate at a clock frequency of 400 MHz and has a throughput of 102.4-Gb/s for 90-nm CMOS technology.
For a cyclic code, the BCH Bound and the Hartmann-Tzeng bound are two of well-known lower bounds for its minimum distance. New bounds are proposed by N. Boston in 2001, that depend on defining set of cyclic code. In this paper, we consider the between the Boston bound and these two bounds for non-binary cyclic codes from numerical examples.
A direct short proof of Horiguchi's formula for error values in alternant codes is provided. Horiguchi's formula employs only output polynomials of Berlekamp-Massey algorithm, which has less computational complexity than extended Euclidean algorithm for decoding alternant codes. As an application of our proof, we provide an explicit formula for the generator and parity check matrices of alternant codes and their singly- and doubly-extended codes.
Haruo OGIWARA Kyouhei SHIMAMURA Toshiyuki SHOHON
This paper proposes methods to improve soft-input and soft-output decoding performance of BCH codes by sum-product algorithm (SPA). A method to remove cycles of length four (RmFC) in the Tanner graph has been proposed. However, the RmFC can not realize good decoding performance for BCH codes which have more than one error correcting capability. To overcome this problem, this paper proposes two methods. One is to use a parity check matrix of the echelon canonical form as the starting check matrix of RmFC. The other is to use a parity check matrix that is concatenation (ConC) of multiple parity check matrices. For BCH(31,11,11) code, SPA with ConC realizes Eb/No 3.7 dB better at bit error rate 10-5 than the original SPA, and 3.1 dB better than the SPA with only RmFC.
Junwoo JUNG Hyungwon PARK Jae-Sung LIM
Cooperation can increase the system performance by obtaining the spatial diversity. While most of the present works concentrate on the analysis of the cooperation based on the inter-user channel response and developing a scheme for higher cooperative diversity, in this paper, we focus on practical resource allocation in OFDMA systems. Since the user who uses the same center frequency can not receive the signal when transmitting, this constraint should be considered to apply the cooperation to OFDMA systems. In this paper, we propose the pair-based OFDMA frame structure that overcomes this constraint. Also in this frame structure to achieve the minimum outage probability of system, we select the best partner among the candidate neighbors and allocate the suitable subchannels to bandwidth requested users through a cooperative subchannel allocation (CSA) algorithm. In order to evaluate the proposed resource allocation scheme, we carry out simulations based on IEEE 802.16e. The simulation results show that our proposed algorithm offers smaller outage probability than one based on non-cooperative communications and we get the minimum outage probability when a threshold for selection of candidate neighbors is 10 dB. We analyze that these results can be achieved by helping users located around the edge of the cell.
We study in this paper the subchannel access and the rate assignment for the multicarrier multi-cell networks. For subchannel access, we show from theoretic results and simulation results that the scheme with only one user per cell in each subchannel outperforms the scheme with multiple users per cell in each subchannel. For rate assignment, a distributed rate assignment is proposed to assign the rate for all subchannels. The proposed rate assignment need not measure the channel gains and uses only local information to iteratively adjust the transmitting power and data rate. We prove that the aggregate rate can be increased by increasing the number of iterations in the proposed rate assignment.