Search

The version of record is available online at: http://dx.doi.org/10.1007/s10623-021-00988-z According to their strength, the tracing properties of a code can be categorized as frameproof, separating, IPP and TA. It is known that, if the minimum distance of the code is larger than a certain threshold then the TA property implies the rest. Silverberg et al. ask if there is some kind of tracing capability left when the minimum distance falls below the threshold. Under different assumptions, several papers have given a negative answer to the question. In this paper, further progress is made. We establish values of the minimum distance for which Reed-Solomon codes do not posses the separating property. This work has been supported by the Spanish Government Grant TCO-RISEBLOCK (PID2019-110224RB-I00) MINECO .

Considering the availability of the global navigation satellite system (GNSS) signals and the increase in its data rate in the future, this paper proposes some new Reed-Solomon coded (RS-coded) orthogonal modulation schemes using the Hadamard codes, as an alternative to the RS-coded code-shift-keying (CSK) modulation in the Quasi-Zenith Satellite System L-band experimental (QZSS-LEX) signals. The simulation result of the proposed schemes shows that, though the frame size and hence the data rate is increased with much reduced complexity in the receiver, the bit error rate performance of RS-coded orthogonal modulation is slightly better than or comparable to the QZSS-LEX.

In the last 10 years, the advancement in the electronics have made possible the development of more sophisticated unmanned vehicles and probes, manufactured using Components-Of-The-Shelf (COTS) available to public, whether be for industrial of scientific purposes. In the matter of aerospace exploration, the CubeSats are the best example of sophisticated devices partially of entirely developed using this commercial COTS. The financial cost of some components is still a point of consideration in the design, but it is not entirely a show-stopper since some low-cost components can be optimized to meet the necessary requirements and increase the reliability. In the case of stratospheric probes and nano-satellites, the Telemetry, Tracking and Command (TT&C) subsystem, in charge of the data uplink/ downlink, can be improved by including an Error Correcting Code (ECC), making possible to use commercial transceivers of low-power are low-cost. In this article we describe an implementation of an interleaved and shortened Reed-Solomon Code, which we called siRS, to improve the image and telemetry downlink in stratospheric probes and nano-satellites, using entirely low-cost commercial RF transceivers and an ARM-based mini-PC.

Aiming to improve the error correction performance of polar codes, researchers have proposed employing the product coding structure involving RS codes of different rates in the horizontal direction and the short polar codewords along the vertical direction. However, there is no efficient algorithm optimizing the rate allocation of RS codes. In order to address this problem, this paper provides an analytical formulation by maximizing the number of correctly decoded information bits. The proposed rate allocation formulation takes the channel statistics into consideration, and we further find that the number of different RS code rates could be limited to a small value. By doing so, the complexities of both the rate allocation optimization and the iterative product decoding could be reduced. Simulation results demonstrate the superiority of RS-polar product codes with the proposed rate allocation method over both additive white Gaussian noise channels and Gilbert–Elliott channels. When the inner polar codes of rate 1/2 are utilized, the optimized RS-polar product codes of low-to-medium rates significantly outperform the successive cancellation decoding of long polar codes, in the regime of a frame error rate ≥10−3.

Các mã Reed-Solomon RS(n, k) là các mã được sử dụng phổ biến nhất hiện nay trong các hệ thống lưu trữ dữ liệu phân tán nhưng chúng có nhược điểm lớn bởi tiêu tốn lượng băng thông khổng lồ khi sửa các lỗi xóa của hệ thống. Phương pháp sửa lỗi xóa cho mã Reed-Solomon bằng cách áp dụng hàm vết do Guruswami và Wootters (Guruswami and Wootters, 2017) đề xuất làm giảm đáng kể băng thông sửa lỗi. Tuy nhiên việc xác định các phác đồ sửa lỗi cho một hoặc nhiều lỗi xóa theo phương pháp này vẫn có độ phức tạp rất lớn ngay cả trên các trường mã hóa nhỏ như F16 , F64 hay F256 . Vì vậy các phương pháp làm giảm độ phức tạp của thuật toán tìm phác đồ sửa lỗi cho mã Reed-Solomon là một vấn đề đáng lưu tâm. Bài báo của chúng tôi đưa ra một số kết quả về giảm độ phức tạp thuật toán tìm phác đồ sửa lỗi xóa cho mã Reed-Solomon, đặc biệt là cho các mã có phần dư n - k = 2., {"references":["Berman, A. & et al. (2021), \"Repairing Reed-Solomon Codes Evaluated on Subspaces,\" 2021 IEEE Int. Symp. Inf. Theory, 2021.","Dau, H., & Milenkovic, O. (2017). Optimal Repair Schemes for Some Families of Full-Length ReedSolomon Codes. Proc. IEEE Int. Symp. Inf. Theory, 346–350.","Dau, H. & et al. (2018). Repairing Reed-Solomon Codes With Multiple Erasures. IEEE Trans. Inf. Theory, 64(10), 6567–6582, doi: 10.1109/TIT.2018.2827942.","Dau, H., & et al. (2021). Repairing Reed-Solomon codes via subspace polynomials. IEEE Trans. Inf. Theory, 67(10), 6395–6407, 2021, doi: 10.1109/TIT.2021.3071878.","Dimakis, A. G. & et al (2010). Network coding for distributed storage systems. IEEE transactions on information theory, 56(9):4539–4551.","Guruswami, V., & Wootters, M. (2017). Repairing Reed-Solomon Codes. IEEE Trans. Inf. Theory, 63(9), 5684–5698.","Li, W. Q., & et al. (2017). A Tradeoff between the Sub-Packetization Size and the Repair Bandwidth for Reed-Solomon Code. 55th annual allerton conference on communication, control, and computing (Allerton), 942–949.","Mardia, J., & et al. (2019). Repairing Multiple Failures for Scalar MDS Codes. IEEE Trans. Inf. Theory, 65(5), 2661–2672, doi: 10.1109/TIT.2018.2876542.","MacWilliams, F. J., & Sloane, N. J. A. (1977). The theory of error-correcting code. Published by: NorthHolland Publishing Company Amsterdam · New York · Oxford.","Li, H., & et al. (2019). On the Sub-Packetization Size and the Repair Bandwidth of Reed-Solomon Codes. IEEE Trans. Inf. Theory, 65(9), 5484–5502.[1] A. Berman, S. Buzaglo, A. Dor, Y. Shany, and I. Tamo, \"Repairing Reed-Solomon Codes Evaluated on Subspaces,\" 2021 IEEE Int. Symp. Inf. Theory, 2021.","Sathiamoorthy, M., & et al. (2013). XORing elephants: Novel erasure codes for big data. Proc. VLDB Endow., 6(5), 325–336, doi: 10.14778/2535573.2488339.","Shanmugam, K. & et al. (2014). A repair framework for scalar MDS codes. IEEE Journal on Selected Areas in Communications, 32(5):998–1007.","Zhang, Y., & et al. (2019). An Improved Cooperative Repair Scheme for Reed-Solomon Codes. Proc. - 2019 19th Int. Symp. Commun. Inf. Technol. Isc. 2019, 525–530, doi: 10.1109/ISCIT.2019.8905159."]}

We consider the $[\text {q}+1,\text {q}-3,5]_{\text {q}}3$ generalized doubly-extended Reed-Solomon code of codimension 4 as the code associated with the twisted cubic in the projective space $\mathrm {PG}(3,\text {q})$ . Basing on the point-plane incidence matrix of $\mathrm {PG}(3,\text {q})$ , we obtain the number of weight 3 vectors in all the cosets of the considered code. This allows us to classify the cosets by their weight distributions and to obtain these distributions. The weight of a coset is the smallest Hamming weight of any vector in the coset. For the cosets of equal weight having distinct weight distributions, we prove that the difference between the w-th components, $3 , of the distributions is uniquely determined by the difference between the 3-rd components. This implies an interesting (and in some sense unexpected) symmetry of the obtained distributions.

The relevance of the topic is determined by the need to increase the speed of data transmission in satellite telecommunication systems through the use of noise-proof coding. The speed of data transmission in a radio channel is actually determined by the level of interference present due to the fact that the radio transmission medium is a public environment and other electronic devices operate in it. The purpose of the article is to develop an algorithm for encoding and decoding the input signal using a multithreshold decoder (MTD) of rigid solutions for subscriber terminals operating with low-orbit spacecraft (NCA), and its comparison with a conventional PC decoder «Messi». The comparison allows us to conclude that the application of the developed algorithm is justified in systems where more stringent requirements are imposed on the probability of an error in the communication channel, while the «Messi» decoder is more appropriate to use in the presence of restrictions on computational complexity

Modern safety-critical systems depend heavily on communication networks while operating in increasingly polluted electromagnetic environments. Forward Error Correction codes are increasingly being used in safety-critical applications; however, vulnerabilities can still be caused by undetected corrupted data. Within this paper, the effectiveness of primitive Reed–Solomon Codes under single-frequency electromagnetic disturbances is assessed. Additionally, the impact of various parameters including the message length, the Reed–Solomon Codes’ symbol size, and the amplitude of the induced voltages are also investigated. Simulations show that, at harmonics and some certain ratios of the bit-rate frequency, the susceptibility of Reed–Solomon Codes relative to this type of disturbance increases substantially. In worse-case scenarios, the rate of undetected corrupted data at these ratios could increase to values above 80%. It is shown that the main reason that Reed–Solomon Codes fail to detect such errors is due to the repetitive nature of code words’ symbols, as well as a special relation among the symbol size, the channel’s bit-rate, and the disturbance frequency. Accordingly, this paper proposes to add an extra inversion layer to the communication protocol to enhance the resiliency of these codes against single-frequency electromagnetic disturbances. Finally, it is shown that the proposed layer substantially mitigates the ratio of undetected corrupted data under the considered electromagnetic environment. By using the proposed approach, the rate of undetected corrupted data at the frequencies of concern decreased to values near 0%. ispartof: Electronics vol:11 issue:9 pages:1-20 status: published

The object of research is the processes of error-correcting coding in telecommunication and computer systems. The main attention is paid to Reed-Solomon (RS) codes, which belong to the very widespread error-correcting codes. Despite the 60-year existence of these codes, the complexity of their decoding still remains a problem. This problem is mainly due to the use of an algebraic approach to their description. The article proposes to use the theory of linear finite-state machine (LFSM) for RS codes as a mathematical basis, which is a combination of the theory of digital filters and finite automaton over nonbinary Galois fields. In the course of research, 12 types of LFSMs are considered for the first time: the recursive LFSMs of 8 types and the non-recursive LFSMs of 4 types. The recursive LFSMs are used for systematic encoding and form a circuit for dividing of polynomials, and the non-recursive LFSMs are used for non-systematic encoding and form a circuit for multiplying of polynomials. All types of LFSMs give the same result for encoding and decoding, but with different complexity, which is impor-tant for practical implementation. The automaton representation is the most suitable for RS codes, since it takes into account the cyclicity property and other features of these codes to the maximum. In contrast to algebraic methods, automaton decoding methods have a simple software and hardware implementation and high performance. With the help of automaton-graphical models, it can accurately estimate the corrective capability of the code. Automaton representation combines known methods of representing Reed-Solomon codes (polynomial, matrix, algebraic) and provides mutual transitions between them. The article attention is spare to the fact that automaton methods for encoding and decoding (n, k)-codes of RS using quantum computers give a gain in time n times.

Recent studies have shown that wireless mesh networks (WMNs) can be cheap, reliable, and efficient solutions for Internet of Things (IoTs) applications and connected devices. However, the increase in the size of the WMNs could lead to a degradation in performance. This makes the network vulnerable to high error rates over noisy and fading channels. This has increased the demand for more efficient channel coding schemes that can provide reliability, high data rate, high coding gain, energy efficiency, and minimum decoding complexity especially for low-cost and special purpose WMNs. In this research, an original multilevel coding with twofold concatenation scheme is designed based on high-rate space-time block codes (HRSTBCs) to cope with this increasing demand, particularly in MIMO-based WMNs. First, a multilevel coding scheme is implemented by correlating HRSTBCs with the uniquely constructed set-partitioning of the transmission matrix, based on the coding gain distance (CGD) criterion. This generates a new scheme, namely multilevel high-rate space-time block code (MHRSTBC), to provide a high transmission rate. Second, a twofold concatenation coding scheme is introduced by concatenating Reed-Solomon (RS) code, has been used for its energy efficiency and optimality in the mobile environment, with the inner code of the associated MHRSTBC. This has formed a new scheme that reaches the maximum coding gains, called the Reed-Solomon multilevel high-rate space-time block code (RS-MHRSTBC). The efficiency of the RS-MHRSTBC is verified by a computer simulation over a Rayleigh flat-fading and additive white Gaussian noise (AWGN) channel. The RS-MHRSTBC is compared with the classical schemes of Alamouti STBC and Multilevel STBC over uncoded QPSK, and the RS-MHRSTBC shows significant high coding gains reached of 47.79 dB, while Alamouti STBC and Multilevel STBC reached 38.12 dB and 44.30 dB at a BER of 10-6 respectively. RS-MHRSTBC also shows a reasonable decoding complexity while maintaining full transmission diversity at spectral efficiency of 2 bits/s/Hz.

Classic Reed-Solomon (RS) codes and binary Bose-Chaudhuri-Hocquenghem (BCH) codes, which can be considered as a special case of RS codes, are utilized for error correction in numerous systems, such as Flash memories, optical communications, wireless communications, magnetic storage, and deep-space probing. Additionally, RS and BCH codes are interleaved/nested to form high-gain coding schemes, including product and product-like codes and the recent generalized integrated interleaved codes, which are among the most promising candidates to address the hyper-speed and excellent-correction-capability requirements posed by next-generation terabit/s digital communications and storage. In recent developments, RS codes are also split/nested/coupled to form locally recoverable erasure codes and minimum storage regenerating codes that substantially improve the efficiency of failure recovery and enable the continued scaling of large-scale distributed storage. In this article, prominent decoder architectures for classic RS/BCH codes are elaborated and the fundamental mathematical reformulations leading to the architectures are explained. Then the challenges and recent advancements on the decoder design of nested RS/BCH codes are highlighted. Erasure-correcting RS decoders for failure recovery are also briefly discussed. The goal of this article is to provide comprehensive understanding of state-of-the-art VLSI architectures for classic RS/BCH codes and introduce the most recent architectures for new coding schemes built by nesting/coupling RS/BCH codes for emerging applications.

© 20xx IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works We prove that there is a Hermitian self-orthogonal k -dimensional truncated generalised Reed-Solomon code of length n¿q2 over Fq2 if and only if there is a polynomial g¿Fq2 of degree at most (q-k)q-1 such that g+gq has q2-n distinct zeros. This allows us to determine the smallest n for which there is a Hermitian self-orthogonal k -dimensional truncated generalised Reed-Solomon code of length n over Fq2 , verifying a conjecture of Grassl and Rötteler. We also provide examples of Hermitian self-orthogonal k -dimensional generalised Reed-Solomon codes of length q2+1 over Fq2 , for k=q-1 and q an odd power of two.

The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised in [Guruswami and Wootters, 2017] on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). Specifically, we show that almost all 2 dimensional RS codes over prime fields (for large enough prime) are asymptotically MSR codes. This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Moreover, we construct several RS codes over prime fields that exhibits efficient repair properties. We also show that unlike the problem of repairing RS codes over field extensions, over prime fields, one can not achieve the cut-set bound with equality. Concretely, by using ideas from additive combinatorics, we improve the cut-set bound by an additive factor, hence showing that every node must transmit more bits than the cut-set bound during a repair. Lastly, we discuss the implications of our results on repairing RS codes for leakage-resilient of Shamir���s secret sharing scheme over prime fields., LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 50:1-50:1

In increasingly electromagnetic-polluted environments, communication networks are becoming more vulnerable. Even networks equipped with error control techniques suffer from this problem. Electromagnetic disturbances can result in corrupted data which are undetectable by error control techniques. Such scenarios are extremely dangerous as the system is unaware of the corruption. This could lead to critical failures. Thus, protecting communication networks against this type of undetected corrupted data is of the utmost importance. In this regard, this paper presents an effective fault elimination approach through encoder tuning. This technique enhances the resiliency of a well-known forward error correction code, known as primitive Reed-Solomon Codes, against steady-state single-frequency electromagnetic disturbances. It is found that this approach outperforms the previously proposed multi-layer inversion-based fault elimination approach in mitigating undetected corrupted data. Furthermore, it is shown that encoder tuning has two main implementation advantages over our previous approach. First, it does not require an extra layer to perform fault elimination. Second, it eliminates the overhead of performing double syndrome calculation at the consumer side. ispartof: pages:433-438 ispartof: 2022 IEEE International Symposium on EMC+SIPI pages:433-438 ispartof: 2022 IEEE International Symposium on EMC+SIPI location:Spokane, Washington, USA date:1 Aug - 5 Aug 2022 status: published

Entanglement-assisted quantum-error-correcting (EAQEC) codes are quantum codes which use entanglement as a resource. These codes can provide better error correction than the (entanglement unassisted) codes derived from the traditional stabilizer formalism. In this paper, we provide a general method to construct EAQEC codes from cyclic codes. Afterwards, the method is applied to Reed–Solomon codes, BCH codes, and general cyclic codes. We use the Euclidean and Hermitian construction of EAQEC codes. Three families have been created: two families of EAQEC codes are maximal distance separable (MDS), and one is almost MDS or almost near MDS. The comparison of the codes in this paper is mostly based on the quantum Singleton bound.

We study the problem of efficiently computing on encoded data. More specifically, we study the question of low-bandwidth computation of functions $F:\mathbb{F}^k \to \mathbb{F}$ of some data $x \in \mathbb{F}^k$, given access to an encoding $c \in \mathbb{F}^n$ of $x$ under an error correcting code. In our model -- relevant in distributed storage, distributed computation and secret sharing -- each symbol of $c$ is held by a different party, and we aim to minimize the total amount of information downloaded from each party in order to compute $F(x)$. Special cases of this problem have arisen in several domains, and we believe that it is fruitful to study this problem in generality. Our main result is a low-bandwidth scheme to compute linear functions for Reed-Solomon codes, even in the presence of erasures. More precisely, let $\epsilon > 0$ and let $\mathcal{C}: \mathbb{F}^k \to \mathbb{F}^n$ be a full-length Reed-Solomon code of rate $1 - \epsilon$ over a field $\mathbb{F}$ with constant characteristic. For any $\gamma \in [0, \epsilon)$, our scheme can compute any linear function $F(x)$ given access to any $(1 - \gamma)$-fraction of the symbols of $\mathcal{C}(x)$, with download bandwidth $O(n/(\epsilon - \gamma))$ bits. In contrast, the naive scheme that involves reconstructing the data $x$ and then computing $F(x)$ uses $\Theta(n \log n)$ bits. Our scheme has applications in distributed storage, coded computation, and homomorphic secret sharing., Comment: 31 pages, 0 figures

International audience; We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an oracle function f : L m Ñ F q , where L Ă F q , a verifier distinguishes whether f is the evaluation of a low-degree polynomial or is far (in relative Hamming distance) from being one, by making only a few queries to f. This topic has been studied in the context of locally testable codes, interactive proofs, probabilistically checkable proofs, and interactive oracle proofs. We present the first interactive oracle proofs of proximity (IOPP) for tensor products of Reed-Solomon codes (evaluation of polynomials with bounds on individual degrees) and for Reed-Muller codes (evaluation of polynomials with a bound on the total degree). Such low-degree polynomials play a central role in constructions of probabilistic proof systems and succinct non-interactive arguments of knowledge with zero-knowledge. For these applications, highly-efficient multivariate low-degree tests are desired, but prior probabilistic proofs of proximity required super-linear proving time. In contrast, for multivariate codes of length N , our constructions admit a prover running in time linear in N and a verifier which is logarithmic in N. For fixed constant number of variables m, the efficiency parameters of our IOPPs for multivariate codes compare well, all things equal, with those of the IOPP for Reed-Solomon codes of [Ben-Sasson et al., ICALP 2018] from which they are directly inspired.

International audience; This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed-Solomon codes, i.e. subcodes of Reed-Solomon codes over $\mathbb{F}_{q^m}$ whose entries lie in a fixed collection of $\mathbb{F}_q$-subspaces of $\mathbb{F}_{q^m}$. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called the twisted product which yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen $\mathbb{F}_q$-subspaces have dimension larger than $m/2$. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger.

This paper investigates the theory of sum-rank-metric codes for which the individual matrix blocks may have different sizes. Various bounds on the cardinality of a code are derived, along with their asymptotic extensions. The duality theory of sum-rank-metric codes is also explored, showing that MSRD codes (the sum-rank analogue of MDS codes) dualize to MSRD codes only if all matrix blocks have the same number of columns. In the latter case, duality considerations lead to an upper bound on the number of blocks for MSRD codes. The paper also contains various constructions of sum-rank-metric codes for variable block sizes, illustrating the possible behaviours of these objects with respect to bounds, existence, and duality properties.

We give constructions of some special cases of [n, k] Reed-Solomon codes over finite fields of size at least n and n + 1 whose generator matrices have constrained support. Furthermore, we consider a generalization of the GM-MDS conjecture proposed by Lovett in 2018. We show that Lovett's conjecture is false in general and we specify when the conjecture is true. Ministry of Education (MOE) Accepted version G.G. was supported by the Singapore Ministry of Education AcademicResearch Fund(Tier 1); grant number: RG127/16.

The problem of Private Information Retrieval (PIR) from coded storage systems with colluding, byzantine, and unresponsive servers is considered. An explicit scheme using an $[n,k]$ Reed-Solomon storage code is designed, protecting against $t$-collusion and handling up to $b$ byzantine and $r$ unresponsive servers, when $n>k+t+2b+r-1$. This scheme achieves a PIR rate of $\frac{n-r-(k+2b+t-1)}{n-r}$. In the case where the capacity is known, namely when $k=1$, it is asymptotically capacity-achieving as the number of files grows. Lastly, the scheme is adapted to symmetric PIR., This is an extended journal version of the ISIT paper arXiv:1802.03731

The parameter identification of channel codes plays a significant role in the fields of adaptive modulation and coding (AMC) as well as non-cooperative communications. In this paper, an algorithm based on probability statistics and Galois field Fourier transform (PS-GFFT) is proposed to identify the parameters of the Reed-Solomon (RS) codes. A threshold obtained by the probability statistics is used to skip wrong parameters within a candidate set, while GFFT is applied to reduce the error identification probability. Meanwhile, the upper bound on correct recognition rate of RS codes has been derived and proved, which quantifies the influence of the received codewords' length, the bit-error-rate of codewords, and the number of bits per symbol on the accuracy of parameters estimation. To the best of our knowledge, the upper bound, which is of great significance in evaluating the performance of recognition algorithms, is provided in this paper for the first time. The numerous simulation results illustrate that the proposed algorithm has better recognition performance than the existing RS codes recognition algorithms. Specifically, the correct recognition probability of the RS codes whose length is no more than 255 can be over 90% when the bit error rate of codewords is below 3 * 10-3, while the conventional algorithms have the best correct recognition probability of 10%. Furthermore, it is observed that the correct recognition rate of our proposed algorithm is close to the derived upper bound, especially for long code length, which further verifies the superiority of our proposed algorithm.

LightChain is the first Distributed Hash Table (DHT)-based blockchain with a logarithmic asymptotic operational complexity, and a distributed storage layer, which preserves its integrity under the corrupted majority power of nodes. Running smart contract-based transactions, however, was a missing feature in the original implementation of LightChain. In this demo paper, we present the software architecture of our open-source smart contract-enabled test network for LightChain., NA

Designing good error correcting codes whose generator matrix has a support constraint, i.e., one for which only certain entries of the generator matrix are allowed to be nonzero, has found many recent applications, including in distributed coding and storage, linear network coding, multiple access networks, and weakly secure data exchange. The dual problem, where the parity check matrix has a support constraint, comes up in the design of locally repairable codes. The central problem here is to design codes with the largest possible minimum distance, subject to the given support constraint on the generator matrix. When the distance metric is the Hamming distance, the codes of interest are Reed-Solomon codes, for which case, the problem was formulated as the "GM-MDS conjecture." In the rank metric case, the same problem can be considered for Gabidulin codes. This thesis provides solutions to these problems and discusses the remaining open problems.

A $k \times n$ matrix over a field is called an MDS (maximum distance separable) matrix if it satisfies the following property: Any $k$ columns of it are linearly independent. Equivalently, its row...

Producción Científica, Entanglement-assisted quantum error correcting codes (EAQECCs) constructed from Reed-Solomon codes and BCH codes are considered in this work. It is provided a complete and explicit formula for the parameters of EAQECCs coming from any Reed-Solomon code, for the Hermitian metric, and from any BCH code with extension degree 2 and consecutive cyclotomic cosets, for both the Euclidean and the Hermitian metric. The main task in this work is the computation of a completely general formula for c, the minimum number of required maximally entangled quantum states., This work was supported in part by the Spanish MICINN/FEDER grants PGC2018-096446-B-C21, PGC2018-096446-B-C22 and RED2018-102583-T, by the Spanish MINECO grant RYC-2016-20208 (AEI/FSE/UE), by the Junta de CyL (Spain) grant VA166G18, by the Generalitat Valenciana (Spain) grant AICO-2019-223 and by Universitat Jaume I grant P1-1B2018-10.

The object of research is the processes of error-correcting coding in telecommunication and computer systems. The main attention is paid to Reed-Solomon codes, which belong to the very widespread error-correcting codes. Despite the 60-year existence of these codes, the complexity of their decoding still remains a problem. This problem is mainly due to the use of an algebraic approach to their description.The article proposes to use the theory of linear finite-state machine (LFSM) for RS codes as a mathematical basis, which is a combination of the theory of digital filters and finite automaton over nonbinary Galois fields. In the course of research, 12 types of LFSMs are considered for the first time: the recursive LFSMs of 8 types and the non-recursive LFSMs of 4 types.The recursive LFSMs are used for systematic encoding and form a circuit for dividing of polynomials, and the non-recursive LFSMs are used for non-systematic encoding and form a circuit for multiplying of polynomials. All types of LFSMs give the same result for encoding and decoding, but with different complexity, which is important for practical implementation.The automaton representation is the most suitable for PC codes, since it takes into account the cyclicity property and other features of these codes to the maximum. In contrast to algebraic methods, automaton decoding methods have a simple software and hardware implementation and high performance. With the help of automaton-graphical models, it can accurately estimate the corrective capability of the code. Automaton representation combines known methods of representing Reed-Solomon codes (polynomial, matrix, algebraic) and provides mutual transitions between them.The article attention is spare to the fact that automaton methods for encoding and decoding (n, k)-codes of RS using quantum computers give a gain in time n times., Объектом исследования являются процессы помехоустойчивого кодирования в телекоммуникационных и компьютерных системах. Основное внимание обращено на коды Рида-Соломона, которые принадлежат к очень распространенным помехоустойчивым кодам. Несмотря на 60-летний период существования этих кодов, пока остается проблемой сложность их декодирования. Эта проблема обусловлена главным образом использованием алгебраического подхода к их описанию.В работе предложено использовать для кодов Рида-Соломона в качестве математической основы теорию линейных последовательностных схем, которая представляет собой сочетание теории цифровых фильтров и конечных автоматов в недвоичных полях Галуа. В ходе исследований впервые рассматриваются 12 типов линейных последовательностных схем: 8 типов рекурсивных линейных последовательностных схем и 4 типа нерекурсивных линейных последовательностных схем. Рекурсивные линейные последовательностные схемы используются для систематического кодирования и образуют схему для деления полиномов, а нерекурсивные линейные последовательностные схемы – для несистематического кодирования и образуют схему для умножения полиномов. Все типы линейных последовательностных схем дают одинаковый результат при кодировании и декодировании, но с различной трудоемкостью, что важно для практической реализации.Автоматное представление является наиболее пригодным для кодов Рида-Соломона, поскольку максимально учитывает свойство цикличности и другие особенности этих кодов. В отличие от алгебраических методов автоматные методы декодирования имеют простую программно-аппаратную реализацию и высокое быстродействие. C помощью автоматно-графовых моделей можно точно оценить корректирующую способность кода. Автоматное представление объединяет известные способы представления кодов Рида-Соломона (полиномиальное, матричное, алгебраическое) и обеспечивает взаимные переходы между ними.В работе обращено внимание, что автоматные методы кодирования и декодирования (n,k)-кодов Рида-Соломона с помощью квантовых компьютеров дают выигрыш во времени в n раз., Об’єктом дослідження є процеси завадостійкого кодування в телекомунікаційних та комп’ютерних системах. Основну увагу звернуто на коди Ріда-Соломона, які належать до найпоширеніших завадостійких кодів. Незважаючи на 60-річний період існування цих кодів, поки що залишається проблемою складність їх декодування. Ця проблема обумовлена головним чином використанням алгебраїчного підходу до їх опису.В роботі запропоновано використати для кодів Ріда-Соломона у якості математичної основи теорію лінійних послідовнісних схем, яка є поєднанням теорії цифрових фільтрів та скінчених автоматів в недвійкових полях Галуа. В ході досліджень вперше розглядаються 12 типів лінійних послідовнісних схем: 8 типів рекурсивних лінійних послідовнісних схем і 4 типи нерекурсивних лінійних послідовнісних схем. Рекурсивні лінійні послідовнісні схеми використовуються для систематичного кодування та утворюють схему для ділення поліномів, а нерекурсивні лінійні послідовнісні схеми – для несистематичного кодування та утворюють схему для множення поліномів. Всі типи лінійних послідовнісних схем дають однаковий результат при кодуванні та декодуванні, але з різною трудомісткістю, що важливо для практичної реалізації.Автоматне представлення є найбільш придатним для кодів Ріда-Соломона, оскільки максимально враховує властивість циклічності та інші особливості цих кодів. На відміну від алгебраїчних методів автоматні методи декодування мають просту програмно-апаратну реалізацію та високу швидкодію. За допомогою автоматно-графових моделей можна точно оцінити коректувальну здатність коду. Автоматне представлення об’єднує відомі способи представлення кодів Ріда-Соломона (поліноміальне, матричне, алгебраїчне) та забезпечує взаємні переходи між ними.В роботі звернуто увагу, що автоматні методи кодування та декодування (n,k)-кодів Ріда-Соломона за допомогою квантових комп’ютерів дають виграш в часі в n разів.

We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding half the minimum distance. When applied to Reed--Solomon or algebraic geometry codes, the algorithm is a reformulation of the so--called {\em power decoding} algorithm. Asymptotically, it corrects errors up to Sudan's radius. In addition, this new framework applies to any code benefiting from an error locating pair. Similarly to Pellikaan's and K\"otter's approach for unique algebraic decoding, our algorithm provides a unified point of view for decoding codes with an algebraic structure beyond the half minimum distance. It permits to get an abstract description of decoding using only codes and linear algebra and without involving the arithmetic of polynomial and rational function algebras used for the definition of the codes themselves. Such algorithms can be valuable for instance for cryptanalysis to construct a decoding algorithm of a code without having access to the hidden algebraic structure of the code.

Представлены результаты разработки каскадного кодека на ПЛИС с внутренним низкоплотностным (НП) кодом стандарта DVB-S2 и внешним кодом Рида-Соломона, позволяющим полностью исключить явление остаточного уровня ошибок.В программируемых логических интегральных схемах (ПЛИС) были реализованы кодер НП-кода с алгоритмом кодирования нерегулярное повторение с накоплением и декодер с модифицированным алгоритмом минимум-сумм . Проведена оценка влияния остаточного уровня ошибок на качество декодирования. Приведены описания разработанной архитектуры, экспериментального стенда и используемые ресурсы ПЛИС., The paper presents the results of the development of a cascade codec on FPGAs with an internal low-density parity-check (LDPC) code of the DVB-S2 standard and an external Reed-Solomon code, that completely eliminates the phenomenon of residual errors. LDPC-code encoder with an irregular repetition with accumulation encoding algorithm and a decoder with a modified minimum sums algorithm were implemented in programmable logic integrated circuits (FPGA). The influence of the residual error level on the decoding quality is estimated. The paper presents the developed architecture, a description of the experimental stand and the FPGA resources., №03(4.3) (2020)

Исследуются различные варианты сигнально-кодовых конструкций (СКК) для скрытных каналов управления беспилотныхлетательных аппаратов в условиях низких углов склонения. Модель канала учитывает мобильность, многолучевость, явление пакетирования ошибок. При построении СКК использован подход, основанный на эквивалентности рассматриваемой модели и некоторой обобщенной модели с пакетированием ошибок и канальным кодированием на основе кодов Рида-Соломона. Получены результаты, подтверждающие целесообразность применения кодов Рида-Соломона., Various variants of signal-code constructions for secretive UAV control channels in the conditions of low declination angles are investigated. The channel model takes into account mobility, multipath, and the phenomenon of error packing. In constructing the signal-code constructions, an approach based on the equivalence of the considered model and some generalized model with error packing and channel coding based on Reed-Solomon codes was used. The results, confirming the feasibility of using Reed-Solomon codes, are obtained., Электросвязь, Выпуск 7 (8) 2020

Distributed storage systems are becoming increasingly ubiquitous in the emerging era of Internet of Things. Major internet technology companies employ large-scale distributed storage systems to accommodate the massive amounts of data generated and requested by global users. The need of reliable and efficient storage of immense amounts of data calls for new applications and development of classical error-correcting codes. This dissertation is devoted to a study of codes with efficient erasure correction for distributed storage systems. The efficiency of erasure correction is often assessed by two performance metrics, bandwidth and locality. In this dissertation we address several problems for each of these two metrics. We construct families of codes with optimal communication complexity for erasure correction ("repair bandwidth") for a heterogeneous storage model, and derive several results for the problem of optimal repair of Reed-Solomon codes. We also construct families of cyclic and convolutional codes with locality, extending the range of parameters for which such families were previously known.

Let PG ( 3 , q ) be the projective space of dimension three over the finite field with q elements. Consider a twisted cubic in PG ( 3 , q ) . The structure of the point-plane incidence matrix in PG ( 3 , q ) with respect to the orbits of points and planes under the action of the stabilizer group of the twisted cubic is described. This information is used to view generalized doubly-extended Reed-Solomon codes of codimension four as asymptotically optimal multiple covering codes.

We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound. In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound. It was previously known that there are Reed-Solomon codes that do not have this property. As an immediate corollary to our main theorem, we obtain better degree bounds on unbalanced expanders that come from Reed-Solomon codes., Comment: 13 pages, several changes in introductory sections

Context. In telecommunications and information systems with an increased noise component the noise-resistant cyclic BCH and Reed-Solomon codes are used. The adjustment and correcting errors in a message require some effective decoding methods. One of the stages in the procedure of decoding RS and BCH codes to determine the position of distortions is the search for the roots of the error locator polynomial. The calculation of polynomial roots, especially for codes with significant correction capacity is a laborious task requiring high computational complexity. That is why the improvement of BCH and RS codes decoding methods providing to reduce the computational complexity is an urgent task. Objective. The investigation and synthesis of the accelerated roots search algorithm of the error locator polynomial presented as an affine polynomial with coefficients in the finite fields, which allows accelerating the process of BCH and RS code decoding. Method. The classical roots search method based on the Chan’s algorithm is performed using the arithmetic of the Galois finite fields and the laborious calculation, in this case depends on the number of addition and multiplication operations. For linearized polynomials, the roots search procedure based on binary arithmetic is performed taking into account the values obtained at the previous stages of the calculation, which provides the minimum number of arithmetic operations. Results. An accelerated algorithm for calculating the values of the error locator polynomial at all points of the GF(2m) finite field for linearized polynomials based on the Berlekamp-Massey method has been developed. The algorithm contains a minimum number of addition operations, due to the use at each stage of the calculations the values obtained at the previous step, as well as the addition in the finite field GF(2). A modified roots search method for affine polynomials over the finite fields has been proposed to determine error positions in the code word while decoding the cyclic BCH and RS codes. Conclusions. The scientific newness of the work is to improve the algorithm of calculating the roots of the error locator polynomial, which coefficients belong to the elements of the finite field. At the same time it simplifies the procedure for cyclic BCH and RS codes decoding, due to reducing the computational complexity of one of the decoding stages, especially finding the error positions using the modified Berlekamp-Massey algorithm. These facts are confirmed by the simulation program results of the roots search of the error locator polynomial algorithm. It is shown, that the application of the accelerated method permits to reach a gain on speed of 1.5 times. Актуальність. У телекомунікаційних та інформаційних системах зв’язку з підвищеною шумовою складової використовуються перешкодостійкі циклічні БЧХ та коди Ріда-Соломона. Коригування та виправлення помилок в повідомленні вимагає ефективних методів декодування. Одним з етапів процедури декодування РС і БЧХ кодів для визначення позицій спотворень є пошук коренів полінома локаторів помилок. Обчислення коренів многочлена, особливо у кодів зі значною коректує здатністю, є трудомісткою завданням, що вимагає високої обчислювальної складності. Тому удосконалення методів декодування БЧХ і РС кодів, що дозволяють зменшити складність обчислень, є актуальним завданням. Мета роботи. Дослідження і синтез прискореного алгоритму пошуку коренів полінома локаторів помилок, представленого у вигляді афінного многочлена з коефіцієнтами в кінцевих полях, який дозволяє прискорити процес декодування БЧХ і РС кодів. Метод. Класичний метод пошуку коренів на базі алгоритму Ченя виконується за допомогою арифметики кінцевих полів Галуа і трудомісткість розрахунків, в даному випадку, залежить від кількості операцій додавання і множення. Для линеаризиваних поліномів процедура пошуку коренів, заснована на двійковій арифметиці та здійснюється з урахуванням значень отриманих на попередніх етапах обчислення, що забезпечує мінімальне число арифметичних операцій. Результати. Розроблено прискорений алгоритм обчислення значень полінома локаторів помилок у всіх точках кінцевого поля GF (2m) для линеаризированих многочленів на базі методу Берлекемпа-Мессі. Алгоритм містить мінімальну кількість операцій додавань, за рахунок використання на кожному етапі обчислень, значень отриманих на попередньому кроці, а також виконання складання в кінцевому полі GF(2). Запропоновано модифікований метод пошуку коренів для афінних поліномів над кінцевими полями, що дозволяє визначити позиції помилок в кодовому слові під час декодування циклічних БЧХ і РС кодів. Висновки. Наукова новизна роботи полягає в удосконаленні алгоритму обчислення коренів многочлена локаторів помилок, коефіцієнти якого належать до елементів кінцевого поля. При цьому спрощується процедура декодування циклічних БЧХ і РС кодів, за рахунок зниження обчислювальної складності одного з етапів декодування – знаходження позицій помилок з використанням модифікованого алгоритму Берлекемпа-Мессі. Дані факти підтверджені результатами програмного моделювання алгоритму пошуку коренів полінома локаторів помилок. Показано, що застосування прискореного методу дозволяє досягти виграшу по швидкодії в 1,5 рази.

Algebraic codes such as BCH code are receiving renewed interest as their short block lengths and low/no error floors make them attractive for ultra-reliable low-latency communications (URLLC) in 5G wireless networks. This article aims at enhancing the traditional adaptive belief propagation (ABP) decoding, which is a soft-in-soft-out (SISO) decoding for high-density parity-check (HDPC) algebraic codes, such as Reed-Solomon (RS) codes, Bose-Chaudhuri-Hocquenghem (BCH) codes, and product codes. The key idea of traditional ABP is to sparsify certain columns of the parity-check matrix corresponding to the least reliable bits with small log-likelihood-ratio (LLR) values. This sparsification strategy may not be optimal when some bits have large LLR magnitudes but wrong signs. Motivated by this observation, we propose a Perturbed ABP (P-ABP) to incorporate a small number of unstable bits with large LLRs into the sparsification operation of the parity-check matrix. In addition, we propose to apply partial layered scheduling or hybrid dynamic scheduling to further enhance the performance of P-ABP. Simulation results show that our proposed decoding algorithms lead to improved error correction performances and faster convergence rates than the prior-art ABP variants. Nanyang Technological University . This work was supported by the Natural Science Foundation of China under Grant 61671128; the Sichuan Key Research and Development Project under Grant 2019YFG0105; the Guangxi Natural Science Foundation under Grant 2018GXNSFAA281161; and the Guangxi Education Department Youth Science Foundation under Grant 2019KY0796. The work of Xiaobei Liu and Yong Liang Guan was supported by Temasek Laboratories@NTU Signal Research Programme Phase 3 Grant DSOCL17187.

In this paper, we consider one-round protocols for reliable message transmission (RMT) when t out of n=2t +1 available channels are controlled by an adversary. We show impossibility of constructing such a protocol that achieves a transmission rate of less than for constant-size messages and arbitrary reliability parameter. In addition, we show how to improve two existing protocols for RMT to allow for either larger messages or reduced field sizes. In this paper, we consider one-round protocols for reliable message transmission (RMT) when t out of n=2t +1 available channels are controlled by an adversary. We show impossibility of constructing such a protocol that achieves a transmission rate of less than for constant-size messages and arbitrary reliability parameter. In addition, we show how to improve two existing protocols for RMT to allow for either larger messages or reduced field sizes.

In this paper, two new decoding algorithms to decode Reed-Solomon codes during transmission over burst Rayleigh fading channels with additive white Gaussian noise (AWGN) are proposed. They only conduct error correction for coded symbols located in the pure AWGN region and conduct error and erasure correction for those symbols located in the burst fading region by treating those coded symbols that are very likely erroneous as erasures. The first algorithm does not need to know the fading locations in advance, while the second algorithm assumes that the fading locations are known. In addition, the performance of such two algorithms is studied when a pre-computed threshold is used to determine the erasures of the code. Simulation results show that our proposed algorithms not only significantly perform better than the classic Berlekamp-Messay algorithm with a comparable computational complexity but also achieve a better tradeoff between the performance and the computational complexity when compared with other existing algorithms. In particular, our algorithms exhibit excellent robustness for tested various code parameters and fading configurations. Furthermore, a more detailed mathematical analysis is also developed in this paper in order to estimate the performance of the new algorithms in the burst Rayleigh fading channels. We observe that the performance of the first algorithm can only be estimated relatively accurately when encountering burst deep-fading, whereas the performance prediction for the second algorithm is always in agreement with the simulation results for various fading cases.

This book is addressed to newcomers to error control coding (ECC), making the subject easy to understand and to apply in a variety of cases. The book begins by presenting in a detailed, step-by-step manner the plethora of parts an ECC system has and the way they interact to achieve the performance required. Contrary to the more abstract and formal approach followed in most books on this topic, this book is unique in that all of the concepts, methods, techniques and algorithms are introduced by way of examples. Thus, the book is almost a workbook, and therefore very suitable for self-study. Readers are encouraged to take an active role while reading, performing calculations as chapters’ progress. Moreover, to reinforce the learning process, many of the topics introduced in the book (Galois fields, Extended Hamming codes, Reed-Solomon codes, interleaving, erasure correction, etc.) are presented in various parts of the book in different ways or contexts. Offers a practical guide to error control coding, accessible to readers with varying backgrounds; Provides newcomers with a sound foundation in error control coding, using a select few topics considered by the author fundamental from an engineering point of view; Presents material with minimal mathematics; Motivates carefully concepts, methods and algorithms making clear the idea behind the conditions for the code to work.

Este trabajo comienza explicando la diferencia entre Teor´ıa de c´odigos y Criptograf´ıa, y de c´omo siendo dos ´areas tan diferentes se pueden fusionar ambas en Criptograf´ıa basada en C´odigos (CBC), una propuesta interesante para resistir ataques con un ordenador cu´antico (Criptograf´ıa post-cu´antica). Estos esquemas requieren de familias de c´odigos con algoritmos eficientes de decodificaci´on y que tengan la propiedad de que sean indistinguibles de un c´odigo lineal aleatorio. En este trabajo vamos a centrarnos en estudiar las familias de c´odigos de evaluaci´on de polinomios. El trabajo contin´ua con el Cap´ıtulo 1, una introducci´on a la Teor´ıa de c´odigos; en particular conceptos de c´odigos lineales, c´ıclicos y restricci´on de c´odigos lineales a otros subcuerpos. Luego, en el Cap´ıtulo 2 nos centramos en algunas familias de c´odigos de evaluaci´on de polinomios. Introducimos estas familias y estudiamos algunas de sus propiedades fundamentales; en particular, los c´odigos Reed-Solomon y sus generalizaciones, para los que explicamos un algoritmo de decodificaci´on eficiente, y los c´odigos Reed-Muller, que son c´odigos de evaluaci´on en varias variables. Finalmente, en el Cap´ıtulo 3, trabajamos con la restricci´on de las familias antes nombradas a subcuerpos m´as peque˜nos, como los c´odigos Goppa, que pueden ser estudiados como la restricci´on de un c´odigo Reed-Solomon generalizado. Adem´as, en este ´ultimo cap´ıtulo explicamos porqu´e siguen siendo interesantes estos ´ultimos c´odigos en criptograf´ıa. This work begins by explaining the difference between Coding Theory and Cryptography, and even being two different areas how they can be merged into Code-based Cryptography (CBC), an interesting proposal to resist attacks from a quantum computer (Post-quantum cryptography). These schemes require a family of codes with an efficient decoding algorithm and which have the property that they are indistinguishable from a random linear code. In this work we will focus on studying the families of polynomial codes. The work continues with Chapter 1, an introduction to Coding theory; in particular concepts of linear codes, cyclic codes and subfield-subcodes. Then, in Chapter 2, we focus on some families of polynomial codes. We introduce these families and we study some of their fundamental properties; in particular, Reed-Solomon codes and their generalizations, for which we explain an efficient decoding algorithm, as well as Reed-Muller codes, which are polynomial codes in several variables. Finally, in Chapter 3, we work with the subfield-subcodes of some of the previously named families, such as Goppa codes, which can be studied as the subfield-subcode of a generalized Reed-Solomon code. Furthermore, in this last chapter we explain why these last codes are still interesting in cryptography.

In this paper, to the best of our knowledge, this is the first time that the generation and reception of online software-reconfigurable real-time 4/16/64-quadrature amplitude modulation (QAM)-encoded and forward error correction (FEC)-enabled orthogonal frequency-division multiplexing (OFDM) signals over X-band fiber-over-radio-based upstream links has been demonstrated. A Reed-Solomon code, i.e., RS (288, 256), with symbol interleaving/deinterleaving is applied to enhance bit-error-rate (BER) performance. The experimental results show that the 4/16/64-QAM-OFDM signals with net data rates of 1.6/3.2/4.8-Gb/s after 1.5-m wireless and 2.26-km SMF-28 transmission with BERs below the hard-decision FEC threshold of 3.8e-3 can be successfully achieved without using FEC. With the help of symbol-interleaved RS code, a post-FEC BER below 1e-8 can be observed when the pre-FEC BER is around 1e-3.

The article describes a method for establishing coding schemes using digital filters. This approach allows to use digital filtering methods (splitting into smaller mode filters, pipelining) for the purpose of changing the code correction capacity. The description of this method has been made for application in the coding of RS codes (Reed-Solomon), hardware encoder device implemented, comparative characteristics provided.

To strengthen the resistance of countermeasures based on secret sharing,several works have suggested to use the scheme introduced by Shamir in 1978, which proposes to use the evaluation of a random d-degree polynomial into n ≥ d + 1 public points to share the sensitive data. Applying the same principles used against the classical Boolean sharing, all these works have assumed that the most efficient attack strategy was to exploit the minimum number of shares required to rebuild the sensitive value; which is d + 1 if the reconstruction is made with Lagrange’s interpolation. In this paper, we highlight first an important difference between Boolean and Shamir’s sharings which implies that, for some signal-to-noise ratio, it is more advantageous for the adversary to observe strictly more than d + 1 shares. We argue that this difference is related to the existence of so-called linear exact repairing codes, which themselves come with reconstruction formulae that need (much) less information (counted in bits) than Lagrange’s interpolation. In particular, this result implies that the choice of the public points in Shamir’s sharing has an impact on the countermeasure strength, which confirms previous observations made by Wang et al. at CARDIS 2016 for the so-called inner product sharing which is a generalization of Shamir’s scheme. As another contribution, we exhibit a positive impact of the existence of linear exact repairing schemes; we indeed propose to use them to improve the state-of-the-art multiplication algorithms dedicated to Shamir’s sharing. We argue that the improvement can be effective when the multiplication operation in the sub-fields is at least two times smaller than that of the base field., IACR Transactions on Cryptographic Hardware and Embedded Systems, Volume 2018, Issue 1

In this dissertation, new algebraic decoding algorithms for Reed���Solomon codes are developed, all of which use reliability information. The two main scenarios are Reed���Solomon codes defined over finite fields and the complex field. For each scenario, we introduce two new algorithms: a syndrome-based and an interpolation-based decoder. For the first scenario, a syndrome-based method which depends on an intermediate decoding result obtained by the extended Euclidean algorithm is investigated. This method is suitable only for high-rate codes, where one or two additionally correctable errors are valuable. The second method in this scenario, utilizes the same intermediate result to perform an interpolation step similar to the Wu algorithm but with a reduced number of interpolation points. As a results, the complexity of the interpolation step is reduced considerably. The second scenario is the decoding of complex-valued Reed���Solomon codes, which recently gained attention in deterministic Compressed Sensing schemes. They allow the use of known algebraic decoding algorithms for sparse vector reconstruction. It is also possible to extract and exploit intrinsic reliability information. The first decoding method for this scenario performs a multi trial error/erasure decoding procedure to enhance the quality of the reliability information. While the other is a list decoder based on both the Guruswami���Sudan algorithm and generelized minimum distance decoding. The performance of all the aforementioned algorithms has been investigated and compared with similar state-of-the-art algorithms. Without exceptions, their performance surpasses that of their counterparts. The second part of this work has been supported by the German research council Deutsche Forschungsgemeinschaft (DFG) under Grant Bo 867/35-1.

Bu tez dört bölümden oluşmaktadır. İlk bölümde, tezin yazımında kullanılacak olan fonksiyon cismi teorisine cebirsel yaklaşım hakkında bilgi verilmiştir. Kodlama teorisinin tarihsel gelişim süreci hakkında bilgi verildikten sonra, fonksiyon cismi teorisiyle olan ilişkisinden bahsedilmiştir. Son olarak, cebirsel geometrik kodların özellikleri ve kodlama teorisindeki yeri ve öneminden bahsedilmiştir. İkinci bölümde, cebirsel yaklaşım kullanılarak fonksiyon cismi teorisinin temel kavramları ve teoremleri verilmiştir. Bu bölümde ana amaç Riemann-Roch teoreminin kanıtını vermektir. Ek olarak, cebirsel geometrik kodların inşası için gerekli olan altyapı oluşturulmuştur. Üçüncü bölümde, kodlama teorisiyle ilgili temel bilgiler verildikten sonra, cebirsel geometrik kodlar incelenmiştir ve parametreleriyle ilgili temel bilgiler verilmiştir. Reed-Solomon, BCH ve "klasik" Goppa kodlarının, cebirsel geometrik kodlar olarak temsil edilebileceği gösterilmiştir. Ardından, kodların asimptotik teorisiyle ilgili temel kavramlar ve sınırlar verildikten sonra asimptotik Tsfasman-Vladut-Zink Sınırı verilmiştir. Son olarak, bir divizörün tabanı kavramı incelenmiştir ve bu kavram yardımıyla cebirsel geometrik kodların tasarlanmış uzaklığı üzerinde elde edilen literatürdeki bir dizi gelişme incelenmiştir. This thesis consists of four chapters. In the first chapter, information about the algebraic approach to the function field theory to be used in writing the thesis is given. After giving information about the historical development process of coding theory, its relationship with the function field theory is discussed. Finally, the properties of algebraic geometric codes and their place and importance in coding theory are mentioned. In the second chapter, basic concepts and theorems of function field theory are given using algebraic approach. The main purpose of this chapter is to prove the Riemann-Roch theorem. In addition, the infrastructure necessary for the construction of algebraic geometric codes is established. In the third chapter, after giving basic information about coding theory, algebraic geometric codes are studied and basic information about their parameters is given. It has been shown that, Reed-Solomon, BCH and "classical" Goppa codes can be represented as algebraic geometric codes. Next, the asymptotic Tsfasman-Vladut-Zink Bound has been given after the basic concepts and bounds related to the asymptotic theory of codes have been given. Finally, the concept of the floor of a divisor is studied and a number of developments on the designed distance of algebraic geometric codes in the literature that obtained with the help of this concept are investigated.

In this study, we present SimCommSys, a simulator of communication systems that we are releasing under an open source license. The core of the project is a set of C + + libraries defining communication system components and a distributed Monte Carlo simulator. Of principal interest is the error-control coding component, where various kinds of binary and non-binary codes are implemented, including turbo, LDPC, repeat-accumulate and Reed–Solomon. The project also contains a number of ready-to-build binaries implementing various stages of the communication system (such as the encoder and decoder), a complete simulator and a system benchmark. Finally, SimCommSys also provides a number of shell and python scripts to encapsulate routine use cases. As long as the required components are already available in SimCommSys, the user may simulate complete communication systems of their own design without any additional programming. The strict separation of development (needed only to implement new components) and use (to simulate specific constructions) encourages reproducibility of experimental work and reduces the likelihood of error. Following an overview of the framework, we provide some examples of how to use the framework, including the implementation of a simple codec, the specification of communication systems and their simulation., peer-reviewed

Reed–Solomon codes and Gabidulin codes have maximum Hamming distance and maximum rank distance, respectively. A general construction using skew polynomials, called skew Reed–Solomon codes, has already been introduced in the literature. In this work, we introduce a linearized version of such codes, called linearized Reed–Solomon codes. We prove that they have maximum sum-rank distance. Such distance is of interest in multishot network coding or in singleshot multi-network coding. To prove our result, we introduce new metrics defined by skew polynomials, which we call skew metrics, we prove that skew Reed–Solomon codes have maximum skew distance, and then we translate this scenario to linearized Reed–Solomon codes and the sum-rank metric. The theories of Reed–Solomon codes and Gabidulin codes are particular cases of our theory, and the sum-rank metric extends both the Hamming and rank metrics. We develop our theory over any division ring (commutative or non-commutative field). We also consider non-zero derivations, which give new maximum rank distance codes over infinite fields not considered before. Reed–Solomon codes and Gabidulin codes have maximum Hamming distance and maximum rank distance, respectively. A general construction using skew polynomials, called skew Reed–Solomon codes, has already been introduced in the literature. In this work, we introduce a linearized version of such codes, called linearized Reed–Solomon codes. We prove that they have maximum sum-rank distance. Such distance is of interest in multishot network coding or in singleshot multi-network coding. To prove our result, we introduce new metrics defined by skew polynomials, which we call skew metrics, we prove that skew Reed–Solomon codes have maximum skew distance, and then we translate this scenario to linearized Reed–Solomon codes and the sum-rank metric. The theories of Reed–Solomon codes and Gabidulin codes are particular cases of our theory, and the sum-rank metric extends both the Hamming and rank metrics. We develop our theory over any division ring (commutative or non-commutative field). We also consider non-zero derivations, which give new maximum rank distance codes over infinite fields not considered before.

This dissertation considers constructions and decoders of several evaluation codes in Hamming and rank metric. Codes in Hamming metric have been studied since the 1950s and the known codes considered in this thesis have found many applications, e.g., satellite communication, CDs, DVDs, BluRays, RAID systems, QR codes, code-based cryptography, and modern storage systems. Rank-metric codes were first introduced in 1978 and have recently become an active research area due to their possible applications in network coding, cryptography, distributed storage systems, low-rank matrix recovery, and space-time coding. In Hamming metric, we propose new partial unique decoding algorithms for decoding interleaved Reed-Solomon and interleaved one-point Hermitian codes beyond half the minimum distance. The algorithms combine ideas of collaborative decoding of interleaved codes and power decoding. For interleaved Reed-Solomon codes, we achieve the same maximal decoding radius as the previous best decoder, but at a better complexity. Our decoder for interleaved one-point Hermitian codes improves upon the previous best maximal decoding radius at all rates. Simulation results for various parameters indicate that both algorithms achieve their maximal decoding radii with high probability for random errors. Inspired by a recent rank-metric code construction by Sheekey, called twisted Gabidulin codes, we present a new code class in Hamming metric: Twisted Reed-Solomon codes. The class contains many maximum distance separable (MDS) codes that are inequivalent to Reed-Solomon codes. We study the duals and Schur squares of the new codes and propose a list decoder that is efficient for many parameters. Furthermore, we single out two subclasses of long non-Reed-Solomon MDS codes and show that there is a subclass resisting some known structural attacks on the McEliece code-based cryptosystem. In rank metric, we present the first sub-quadratic runtime half-the-minimum-distance decoding algorithm for Gabidulin codes, a well-known class of maximum rank distance (MRD) codes that can be seen as the rank-metric analog of Reed-Solomon codes. The result is achieved by accelerating many operations over skew polynomial rings that occur in a known decoding algorithm. Further, we show that the core steps of several known decoding algorithms for interleaved Gabidulin codes, both key-equation- and interpolation-based, can be implemented using row reduction of skew polynomial matrices. By adapting well-known row-reduction algorithms over ordinary polynomial rings to skew polynomials, we achieve conceptually simple and in some cases faster decoding algorithms. The approach is inspired by several recent publications that found a unified description of various decoders of Reed-Solomon, one-point Hermitian, and their interleaved codes. Finally, we propose a generalization of Sheekey's twisted Gabidulin codes, using similar methods as for our twisted Reed-Solomon codes. The new code class contains many MRD codes that are inequivalent to both Gabidulin codes and the original twisted Gabidulin codes.

For a linear maximum distance separable (MDS) code with redundancy $r$ , the covering radius is either $r$ or $r-1$ . However, for $r>3$ , few examples of $q$ -ary linear MDS codes with radius $r-1$ are known, including the Reed–Solomon codes with length $q+1$ . In this paper, for redundancies $r$ as large as $\sqrt [{12}]{q}$ , infinite families of $q$ -ary MDS codes with covering radius $r-1$ and length less than $q+1$ are constructed. These codes are obtained from algebraic-geometric codes arising from elliptic curves. For most pairs $(r,q)$ with $r\le \sqrt [{12}]{q}$ , these are the shortest $q$ -ary MDS codes with covering radius $r-1$ .