Theses supervised by Prof. Dr. Erdal Arıkan
13 theses · İhsan Doğramacı Bilkent University
Optik haberleşme için uç uca eklemeli kutupsal reed-solomon kodlar
A concatenated forward error correcting (FEC) code is developed by targeting optical communications. Polar and product Reed-Solomon (RS) codes are used as inner and outer codes, respectively. An interleaver block is designed to align multiple inner code blocks. Target key parameter indicators (KPIs) for the decoder circuitry are set to 1 Tb/s throughput and 10 mm2 area occupation. These KPIs narrowed the design space down to the simplest decoding algorithms in moderate block-lengths. Soft information from the channel is collected by a polar decoder. Minimum distance between codewords is increased by a product code with two error correcting RS codes. Performance of the developed FEC code is evaluated based on its communications performance, decoding complexity and area occupation. Code configurations are designed with overheads of 15%, 20%, 24% and 28% supporting 1 Tb/s throughput. In one configuration, 11.3 dB net coding gain is estimated at 10−15 bit error rate (BER). Area of the decoder circuitry is estimated to be 14.27 mm2 in 28nm while supporting 1 Tb/s throughput.
Yüksek veri hızlı reed-solomon çarpım kodların ASIC üzerinde gerçeklenmesi
A detailed ASIC implementation study of a decoder architecture for the product of two Reed-Solomon (RS) codes is presented. The implementation aims to achieve high throughput (more than 1 Tb/s) under low power and area consumption constraints while having more than 9 dB coding gain compared to uncoded transmission when concatenated with an inner polar code. The scope of work includes a comprehensive design space exploration for very high rate RS codes. Novel algorithms and architectures are introduced to achieve the design goals. High-throughput is achieved through a combination of pipelining and unrolling methods, while a fully-automated register balancing technique is used to minimize the implementation complexity. The implementation has been carried out using the 28nm TSMC library.
Ardışık kod çözümü kullanarak birleşik kaynak kanal kodlama
ABSTRACT JOINT SOURCE CHANNEL CODING USING SEQUENTIAL DECODING Bekir Ahmet Doğrusöz M.S. in Electrical and Electronics Engineering Supervisor: Prof. Dr. Erdal Arıkan August 1997 In systems using conventional source encoding, source sequence is changed into a series of approximately independent equally likely binary digits. Perfor mance of a code is bounded with the rate distortion function and improves as the redundancy of the encoder output is decreased. However decreasing the redundancy implies increasing the block length and hence the complexity. For the systems requiring low complexity at transmitter, joint source chan nel (JSC) coding can be successfully used for direct encoding of source into the channel for lossless recovery. In such a system, without any distortion, compression depends on the redundancy of the source, and is bounded by the Renyi entropy of the source. In this thesis we analyze transmission of English text with a JSC coding system. Written English is a good example for sources with natural redundancy. Since we are unable to calculate the Renyi entropy of written English, we obtain estimates and compare with the experimental results. We also work on an alternative source encoding method for accuracy- compression trade-off in joint source channel coding systems. The pro posed stochastic distortion encoder (SDE) is capable of achieving accuracy- compression trade-off at any average distortion constraint with very low block lengths, and hence performs better than or as good as an equivalent rate distor tion encoder. As block length approaches infinity the performance of stochastic distortion encoder approaches rate distortion function. Formulations for opti mal SDE design and results for block lengths 1,2 and 3 are also given. Keywords : Coding, Information Theory, Lossy Source Encoding, Joint Source- Channel Decoding, Sequential Decoding. m
Dağıtık kaynak kodlama için kutupsal kodlar
Polar codes were invented by Arıkan as the first "capacity achieving" codes for binary-input discrete memoryless symmetric channels with low encoding and decoding complexity. The "polarization phenomenon", which is the underlying principle of polar codes, can be applied to different source and channel coding problems both in single-user and multi-user settings. In this work, polar coding methods for multi-user distributed source coding problems are investigated. First, a restricted version of lossless distributed source coding problem, which is also referred to as the Slepian-Wolf problem, is considered. The restriction is on the distribution of correlated sources. It is shown that if the sources are "binary symmetric" then single-user polar codes can be used to achieve full capacity region without time sharing. Then, a method for two-user polar coding is considered which is used to solve the Slepian-Wolf problem with arbitrary source distributions. This method is also extended to cover multiple-access channel problem which is the dual of Slepian-Wolf problem. Next, two lossy source coding problems in distributed settings are investigated. The first problem is the distributed lossy source coding which is the lossy version of the Slepian-Wolf problem. Although the capacity region of this problem is not known in general, there is a good inner bound called the Berger-Tung inner bound. A polar coding method that can achieve the whole dominant face of the Berger-Tung region is devised. The second problem considered is the multiple description coding problem. The capacity region for this problem is also not known in general. El Gamal-Cover inner bound is the best known bound for this problem. A polar coding method that can achieve any point on the dominant face of El Gamal-Cover region is devised.
Sıralı elemeli ve listeli kutupsal kodçözücü'nün FPGA uygulaması
Polar Codes are the first asymptotically provably capacity achieving error correc- tion codes under low complexity successive cancellation (SC) decoding for binary discrete memoryless symmetric channels. Although SC is a low complexity algo- rithm, it does not provide as good performance as a maximum-likelihood (ML) decoder, unless sufficiently large code block is used. SC is a soft decision decod- ing algorithm such that it employs depth-first searching method with a divide and conquer approach to find a sufficiently perfect estimate of decision vector. Using SC with a list (SCL) improves the performance of SC decoder such that it provides near ML performance. SCL decoder employs beam search method as a greedy algorithm to achieve ML performance without considering all possible codewords. The ML performance of polar codes is not good enough due to the minimum hamming distance of possible codewords. For the purpose of increas- ing the minimum distance, cyclic redundancy check aided (CRC-SCL) decoding algorithm can be used. This algorithm makes polar codes competitive with state of the art codes by exchanging complexity with performance. In this thesis, we present an FPGA implementation of an adaptive list decoder; consisting of SC, SCL and CRC decoders to meet with the tradeoff between performance and complexity.
Optik haberleşmeler için kutupsal kodlar
Optical communication systems have become the backbone of long distance communication networks due to their ability to transport data at high rates. A typical modern optical communication system should be capable to achieve data rates of 100 Gb/s or beyond. At such a high data rate, it is not feasible to retransmit the corrupted data. For reliable communication at improved power efficiency, communication systems use forward error correction (FEC) schemes. FEC schemes should have low latency to provide high throughput and good error performance to achieve an output bit error rate (BER) of $ 10E-15 $ or lower in optical channels. Moreover, implementation schemes of these FEC codes should be simple, as telecommunications equipments in optical access networks can only accommodate restricted hardware complexity. In this contribution, we study existing ITU-T G.975.1 recommended FEC schemes and recently proposed state-of-the-art FEC codes for optical networks. Next, we analyze polar codes, a recently proposed class of error-correcting codes with advantageous properties in terms of error performance, structure, latency and design method. Throughout our analysis we assume that optical channels can be modeled as additive white Gaussian noise (AWGN) channels. We investigate whether polar codes can compete with the above mentioned FEC schemes in the arena of optical communications. We conclude that polar codes outdo all G.975.1 recommended FEC codes in terms of error performance with the same overhead and relatively shorter block lengths. We also highlight some of the issues/aspects which need to be addressed to enhance the error performance of polar codes at finite block lengths so that they can catch up with (or surpass) recently proposed third generation FEC codes. Most of the proposed FEC codes for next generation optical networks are based on LDPC and turbo codes. Unfortunately, these codes have error floors at very low BER. Post-processing algorithms along with special construction techniques for these codes are proposed in literature to suppress their error floors. These special designs improve their error performance at the cost of extra complexity. Luckily, polar codes do not suffer from error floor problem in low BER regions. Moreover, polar codes have regular structure which makes its hardware implementation simple. There are various polar decoders proposed in literature with desirable properties in terms of error performance and complexity. These features make polar code an attractive candidate to be thoroughly analyzed for application in optical communications. Our analysis of polar codes in this thesis is restricted to its successive cancellation (SC) decoding as it provides a nice balance between complexity and error performance. Error performance of polar codes with larger and moderate block lengths cannot be determined explicitly by Monte Carlo (MC) simulations for optical communication systems operating at high signal to noise ratio (SNR) due to prohibitive simulations time. To make sure that polar codes perform well in low BER regions, we use analytical methods to find bounds on their error rate. We use density evolution (DE) with Gaussian approximation (GA) for the construction and error performance estimation of polar codes. We conclude that DE-GA is a reliable algorithm for construction and error performance evaluation of polar codes by observing that our results obtained with simulations and DE-GA algorithm in low SNR region agree close enough to expect that there will not be too much deviation in high SNR region. The performance of a code in optical communications is usually described by its net coding gain (NCG). Using Shannon's performance limits, maximum value of NCG that a FEC can achieve asymptotically can be calculated . But comparing the performance of a finite length code to the asymptotic performance of a FEC is not fair. Therefore in this thesis, we calculate the maximum NCG that can be achieved by a FEC with finite block length to make our performance comparisons more meaningful.
Kutupsal kodlar için yüksek enerji verimliliğine ve düşük gecikmeye sahip yüksek veri hızlı kod çözme metod ve mimarileri
Polar coding is a low-complexity channel coding method that can provably achieve Shannon's channel capacity for any binary-input discrete memoryless channels (B-DMC). Apart from the theoretical interest in the subject, polar codes have attracted attention for their potential applications. We propose high throughput and energy-efficient decoders for polar codes using combinational logic targeting, but not limited to, next generation communication services such as optical communications, Massive Machine-Type Communications (mMTC) and Terahertz communications. First, we propose a fully combinational logic architecture for Successive-Cancellation (SC) decoding, which is the basic decoding method for polar codes. The advantages of this architecture are high throughput, high energy-efficiency and flexibility. The proposed combinational SC decoder operates at very low clock frequencies compared to synchronous (sequential logic) decoders, but takes advantage of the high degree of parallelism inherent in such architectures to provide a higher throughput and higher energy-efficiency compared to synchronous implementations. We provide ASIC and FPGA implementation results to present the characteristics of the proposed architecture and show that the decoder achieves approximately 2.5 Gb/s throughput with a power consumption of 190 mW with 90 nm 1.3 V technology and block length of 1024. We also provide analytical estimates for complexity and combinational delay of such decoders. We explain the use of pipelining with combinational decoders and introduce pipelined combinational SC decoders. At longer block lengths, we propose a hybrid-logic SC decoder that combines the advantageous aspects of the combinational and synchronous decoders. In order to improve the throughput further, we use weighted majority-logic decoding for polar codes. Unlike SC decoding, majority-logic decoding fails to achieve channel capacity, but offers better throughput due its parallelizable schedule. We give a novel recursive description for weighted majority-logic decoding for bit-reversed polar codes and use the proposed definition for implementations without determining the check-sums individually as done in conventional majoritylogic decoding. We demonstrate by analytical estimates that the complexity and latency of the proposed architecture are O(Nlog2 3) and O(log2 2 N), respectively. Then, we validate the calculated estimates by a fully combinational logic implementation on ASIC. For a block length of 256, the implemented decoders achieve 17 Gb/s throughput with 90 nm 1.3 V technology. In order to compensate the error performance penalty of the majority-logic decoding, we propose novel hybrid decoders that combine SC and weighted majority-logic decoding algorithms. We demonstrate that very high latency gains can be obtained by such decoders with small error performance degradation with respect to SC decoding.
Model tabanlı fountaın kodları kullanarak hataya dayanıklı stereo video akıtımı
Error resilient digital video streaming has been a challenging problem since the introduction and deployment of early packet switched networks. One of the most recent advances in video coding is observed on multi-view video coding which suggests methods for the compression of correlated multiple image sequences. The existing multi-view compression techniques increase the loss sensitivity and necessitate the use of efficient loss recovery schemes. Forward Error Correction (FEC) is an efficient, powerful and practical tool for the recovery of lost data. A novel class of FEC codes is Fountain codes which are suitable to be used with recent video codecs, such as H.264/AVC, and LT and Raptor codes are practical examples of this class. Although there are many studies on monoscopic video, transmission of multi-view video through lossy channels with FEC have not been explored yet. Aiming at this deficiency, an H.264-based multi-view video codec and a model-based Fountain code are combined to generate an efficient error resilient stereoscopic streaming system. Three layers of stereoscopic video with unequal importance are defined in order to exploit the benefits of Unequal Error Protection (UEP) with FEC. Simply, these layers correspond to intra frames of left view, predicted frames of left view and predicted frames of right view. The Rate-Distortion (RD) characteristics of these dependent layers are defined by extending the RD characteristics of monoscopic video. The parameters of the models are obtained with curve fitting using the RD samples of the video, and satisfactory results are achieved where the average difference between the analytical models and RD samples is between 1.00% and 9.19%. An heuristic analytical model of the performance of Raptor codes is used to obtain the residual number of lost packets for given channel bit rate, loss rate, and protection rate. This residual number is multiplied with the estimated average distortion of the loss of a single Network Abstraction Layer (NAL) unit to obtain the total transmission distortion. All these models are combined to minimize the end-to-end distortion and obtain optimal encoder bit rates and UEP rates. When the proposed system is used, the simulation results demonstrate up to 2dB increase in quality compared to equal error protection and only left view error protection. Furthermore, Fountain codes are analyzed in the finite length region, and iterative performance models are derived without any assumptions or asymptotical approximations. The performance model of the belief-propagation (BP) decoder approximates either the behavior of a single simulation results or their average depending on the parameters of the LT code. The performance model of the maximum likelihood decoder approximates the average of simulation results more accurately compared to the model of the BP decoder. Raptor codes are modeled heuristically based on the exponential decay observed on the simulation results, and the model parameters are obtained by line of best fit. The analytical models of systematic and non-systematic Raptor codes accurately approximate the experimental average performance.
OFDM için frekans ve zaman seçici kanallarda düşük karmaşıklı eşleme
In current standards Orthogonal Frequency Division Multiplex -OFDM- is widelyused for its high resistance to multi-path environments and high spectral efficiency. However since the transmission duration is longer, it is affected fromtime variations of the channel more than single carrier systems. Orthogonality ofsub-carriers are lost within an OFDM symbol and intercarrier interference(ICI)occurs as a result of time variation of the channel. Channel estimation and equalizationbecome problematic, because the classical structures like MMSE requirevery complex operations. This thesis studies the channel equalization problem,as separate from the channel estimation problem. The thesis assumes that thechannel coeffcients are perfectly known and focuses on the estimation of datatransmitted on each OFDM carrier. First, a survey of existing algorithms onchannel equalization is given and simulations are provided to compare them interms of complexity and performance under an OFDM system scenario that isconsistent with the present WiMAX system parameters and operating conditions.As a novel contribution, the thesis proposes two new equalization methods byamending existing algorithms and shows that these modified algorithms improve the state-of-the-art in channel equalization in terms of complexity and performanceunder certain high-mobility scenarios. Ultimately it is shown that theintercarrier interference cancellation problem remains a major impediment tothe implementation of OFDM in high-mobility environments.
Kutuplaşma kodlarının evrişimli turbo kodlar ile başarım karşılaştırması
Polar codes introduced recently by Arıkan are the first low-complexitycodes achieving symmetric capacity for arbitrary binary-input discretememoryless channels (B-DMCs). Although being theoreticallysignificant, their practical significance is an issue that has not yetbeen fully explored. Previous studies have compared polar codes withReed-Muller codes, where it was found that polar codes can outperformthem. In this thesis, to investigate how polar codes perform againststate-of-the-art forward error correction (FEC) codes used inpractice, we implement a IEEE 802.16 based link-level WorldwideInteroperability for Microwave Access (WiMAX) simulator whichincorporates several WiMAX FEC options, and polar codes. IEEE 802.16standards family define standards for current and next generationbroadband wireless access, which will make high data rate multimediaapplications in mobile environments a reality. Next generationbroadband access standard, pursued by the IEEE 802.16 Task Group m isa work in progress, and requires even more sophisticated errorcorrection schemes so that higher throughput, better QOS, highermobilities, wider ranges and lower latencies are supported. We performperformance comparison simulations with the convolutional turbo codes(CTC) configurations defined in IEEE 802.16e to see how much of aperformance gap exists between polar codes and CTCs. The main findingsof the thesis are that, although the polar codes achieve capacity forspecific conditions, as expected, for the code lengths and channelconditions we have simulated, the performance of them cannot competewith that of the CTCs with equivalent rates and lengths. It remains atask to see whether polar codes can achieve similar performances withCTCs when used as component codes in other configurations and aid inthe advancement of new communication technologies.
Sistem seviyesinde WiMAX simulasyonu çalışması
In this thesis, we implement a WiMAX system level simulator compliant with the evaluation methodology document published by the IEEE 802.16m Task Group. We study the PHY abstraction of polar codes and integrate polar codes intothe simulator. We compare the system level performances of polar code and convolutional turbo code (CTC) and observe that CTC outperforms polar code.On the simulator, we study the downlink (DL) performance of WiMAX under various configurations such as scheduling methods, subchannelization methods, andfrequency reuse models. We study there types of scheduling methods, namely round robin (RR) scheduling, proportional fair (PF) scheduling, and maximum sum rate (MSR) scheduling. We observe that MSR scheduling has the best throughput performance but does not support the users far from the base station. We study three frequency reuse models, namely 1X3X1, 1X3X3, and 3X3X1. We observe that 1X3X1 reuse model has the best throughput performance and maximum spectral efficiency is obtained in 1X3X3 reuse model. We study two subchannelization methods, namely PUSC and band AMC. We observe thatin low mobility cases, band AMC outperforms PUSC and in high mobility cases,PUSC is better than band AMC.
Kutupsal ve polarizayson ayarlı evrişimli (PAC) kodlarının performans ve hesaplama analizi
We study the performance of sequential decoding of polarization-adjusted convolutional (PAC) codes. We present a metric function that employs bit-channel mutual information and cutoff rate values as the bias values and significantly reduces the computational complexity while retaining the excellent error-correction performance of PAC codes. With the proposed metric function, the computational complexity of sequential decoding of PAC codes is equivalent to that of conventional convolutional codes. Our results indicate that the upper bound on the sequential decoding computational complexity of PAC codes follows a Pareto distribution. We also employ guessing technique to derive a lower bound on the computational complexity of sequential decoding of PAC codes. To reduce the PAC sequential decoder's worst-case latency, we restrict the number of searches executed by the sequential decoder. We introduce an improvement to the successive-cancellation list (SCL) decoding for polarized channels that reduces the number of sorting operations without degrading the code's error-correction performance. In an SCL decoding with an optimum metric function, we show that, on average, the correct branch's bit-metric value must be equal to the bit-channel capacity. On the other hand, the average bit-metric value of a wrong branch can be at most $0$. This implies that a wrong path's partial path metric value deviates from the bit-channel capacity's partial summation. This enables the decoder to identify incorrect branches and exclude them from the list of metrics to be sorted. We employ a similar technique to the stack algorithm, resulting in a considerable reduction in the stack size. Additionally, we propose a technique for constructing a rate profile for PAC codes of arbitrary length and rate which is capable of balancing the error-correction performance and decoding complexity of PAC codes. For signal-to-noise ratio (SNR) values larger than a target SNR value, the proposed approach can significantly enhance the error-correction performance of PAC codes while retaining a low mean sequential decoding complexity. Finally, we examine the weight distribution of PAC codes with the goal of providing a new demonstration that PAC codes surpass polar codes in terms of weight distribution.
Kutupsal ve polarizayson ayarlı evrişimli (PAC) kodlar için fano çözücüsünün donanım uygulaması
Polarization-adjusted convolutional (PAC) codes are a new class of error-correcting codes that have been shown to achieve near-optimum performance. By combining ideas from channel polarization and convolutional coding, PAC codes create an overall encoding transform that achieves a performance near the information-theoretic limits at short block lengths. In this thesis we propose a hardware implementation architecture for Fano decoding of PAC codes. First, we introduce a new variant of Fano algorithm for decoding PAC codes which is suitable for hardware implementation. Then we provide the hardware diagrams of the sub-blocks of the proposed PAC Fano decoder and an estimate of their hardware complexity and propagation delay. We also introduce a novel branch metric unit for sequential decoding of PAC codes which is capable of calculating the current and previous branch metric values online, without requiring any storage element or comparator. We evaluate the error-correction performance of the proposed decoder on FPGA and its hardware characteristics on ASIC with TSMC 28 nm 0.72 V library. We show that, for a block length of 128 and a message length of 64, the proposed decoder can be clocked at 500 MHz and achieve approximately 38.1 Mb/s information throughput at 3.5 dB signal-to-noise ratio with a power consumption of 3.85 mW.