S(5,8,24) is one of the largest known Steiner systems and connects combinatorial designs, error-correcting codes, finite simple groups, and sphere packings in a truly remarkable way. This thesis discusses the underlying structure of S(5,8,24), its construction via the (24,12) Golay code, as well its automorphism group, which is the Mathieu group M24, a member of the sporadic simple groups. Particular attention is paid to the calculation of the size of automorphism groups of Steiner systems using the Orbit-Stabilizer Theorem. We conclude with a section on the sphere packing problem and elaborate on how the 8-sets of S(5,8,24) can be used to form Leech's Lattice, which Leech used to create the densest known sphere packing in 24-dimensions. The appendix contains code written for Matlab which has the ability to construct the octads of S(5,8,24), permute the elements to obtain isomorphic S(5,8,24) systems, and search for certain subsets of elements within the octads. / Master of Science

The errors that can occur in a computer system during data reading or recording in the memory can be of different types depending upon the memory organization. They can be random bit errors or burst errors. Therefore, if high reliability is required, the use of an error correcting technique that will be able to handle both types of errors is necessary. In this study the capability of some classes of error correcting codes is analysed and their performance with both types of errors is tested. Reed Solomon and concatenated codes are examined in more detail because they are known to be among the best classes of codes. In order to evaluate the performance of these codes two well known classes of codes are used: BCH codes and Fire codes. The performance of all the codes with regard to random error correction is analysed using a binary symmetric channel model. BCH codes are shown to be more powerful for average codeword length, but as the codeword length increases RS and concatenated codes perform better than BC3 codes of the same rate of transmission. A new model for systems with burst errors is introduced with which a large variety of real systems can be simulated by choosing the appropriate distributions of burst errors. The performance of all these codes at correcting burst errors is simulated using this model. It is shown that RS codes and concatenated codes are very powerful with burst errors and can increase significantly the reliability of a signaling system incorporating these types of errors. An advantage of RS codes compared to concatenated codes is that they can be very easily implemented and can be employed efficiently for systems with any codeword length. Concatenated codes can perform better than RS codes only when very long codewords are required. / M.S.

The Bose-Chaudhuri-Hocquenghem (BCH) codes are best constructive codes for channels in which error affect successive symbols independently. The binary BCH codes, a subclass of BCH codes, are known to have good random error correcting capability and Reed-Solomon (RS) codes, an important subclass of BCH codes, have very good burst error correcting capability. A concatenation of these two codes, the binary BCH/RS concatenated codes, can correct both random and burst errors. The decoding procedure for these codes is well documented. However not much work has been done on the implementation of the decoding procedure. This thesis deals with development of configurations for decoding binary BCH codes, RS codes and BCH/RS concatenated codes. The decoding procedure is first described. Sample calculations are shown to explain the decoding procedure. The decoding procedure consists of (1) 3 major steps for binary BCH codes and (2) 4 major steps for RS codes. Each of these steps can be implemented by either hardware or software, but the efficiency varies between the specific steps of the de- coding procedure. For each step, both hardware and software implementations are discussed. The complexity and decoding delay for both methods of implementation are determined. The optimal combination, which offers fast execution time and overall system simplicity, is presented. A new procedure for designing BCH/RS concatenated codes is developed and presented in Chapter VI. The advantages of this new procedure are also discussed in Chapter VI. / M.S.

The paradigm of network coding was introduced as a means to conserve bandwidth (or equivalently increase throughput) in information flow networks. Network coding makes use of the fact that unlike physical commodities, information can be replicated and coded together at the nodes of the network. As a result, routing can be strictly suboptimal in many classes of information flow networks compared to network coding. Network-error correction is the art of designing network codes such that the sinks of the network will be able to decode the required information in the presence of errors in the edges of the network, known as network-errors. The network coding problem on a network with given sink demands can be considered to have the following three major subproblems, which naturally also extend to the study of network-error correcting codes, as they can be viewed as a special class of network codes (a) Existence of a network code that satisfies the demands (b) Efficient construction of such a network code (c) Minimum alphabet size for the existence of such a network code. This thesis primarily considers linear network coding and error correction and in- vestigates solutions to these issues for certain classes of network coding and error correction problems in acyclic networks. Our contributions are broadly summarised as follows. (1) We propose the use of convolutional codes for multicast network-error correc- tion. Depending upon the number of network-errors required to be corrected in the network, convolutional codes are designed at the source of the multicast network so that these errors can be corrected at the sinks of the networks as long as they are separated by certain number of time instants (for which we give a bound). In con- trast to block codes for network-error correction which require large field sizes, using convolutional codes enables the field size of the network code to be small. We discuss the performance of such networks under the BSC edge error model. (2)Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. In our work, we give an algorithm which, starting from a given network-error correcting code, can obtain an- other network code using a small field, with the same error correcting capability as the original code. The major step in our algorithm is to find a least degree irreducible poly- nomial which is coprime to another large degree polynomial. We utilize the algebraic properties of finite fields to implement this step so that it becomes much faster than the brute-force method. A recently proposed algorithm for network coding using small fields can be seen as a special case of our algorithm for the case of no network-errors. (3)Matroids are discrete mathematical objects which generalize the notion of linear independence of sets of vectors. It has been observed recently that matroids and network coding share a deep connection, and several important results of network coding has been obtained using these connections from matroid theory. In our work, we establish that matroids with certain special properties correspond to networks with error detecting and correcting properties. We call such networks as matroidal error detecting (or equivalently, correcting) networks. We show that networks have scalar linear network-error detecting (or correcting) codes if and only if there are associated with representable matroids with some special properties. We also use these ideas to construct matroidal error correcting networks along with their associated matroids. In the case of representable matroids, these algorithms give rise to scalar linear network- error correcting codes on such networks. Finally we also show that linear network coding is not sufficient for the general network-error detection (correction) problem with arbitrary demands. (4)Problems related to network coding for acyclic, instantaneous networks have been extensively dealt with in the past. In contrast, not much attention has been paid to networks with delays. In our work, we elaborate on the existence, construction and minimum field size issues of network codes for networks with integer delays. We show that the delays associated with the edges of the network cannot be ignored, and in fact turn out to be advantageous, disadvantageous or immaterial, depending on the topology of the network and the network coding problem considered. In the process, we also show multicast network codes which involve only delaying the symbols arriving at the nodes of the networks and coding the delayed symbols over a binary field, thereby making coding operations at the nodes less complex. (5) In the usual network coding framework, for a given set of network demands over an arbitrary acyclic network with integer delays assumed for the links, the out- put symbols at the sink nodes, at any given time instant, is a Fq-linear combination of the input symbols generated at different time instants where Fq denotes the field over which the network operates. Therefore the sinks have to use sufficient memory elements in order to decode simultaneously for the entire stream of demanded infor- mation symbols. We propose a scheme using an ν-point finite-field discrete fourier transform (DFT) which converts the output symbols at the sink nodes at any given time instant, into a Fq-linear combination of the input symbols generated during the same time instant without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into ν-instantaneous networks (ν is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (non-transform) approach if and only if there exists a network code satisfying sink demands in the transform approach.

Thesis: B.S., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 1977 / Includes bibliographical references. / by Alan Dale Siggia. / B.S. / B.S. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science

Sveriges ökade engagemang i internationella konflikter har förändrat under vilkaformer och i vilka miljöer som dagens militära operationer genomförs. Framföralltinnebär det att alla insatsförband inom Försvarsmakten ska kunna verka inom allakonfliktnivåer och i de flesta miljöer, även i urban terräng. Som en följd av dettauppkommer nya behov och krav på den indirekta bekämpningsförmågan i form avprecisionsbekämpning. Syftet med föreliggande arbete är att kartlägga om, och till vilken grad, ettkurskorrigerande tändrör bidrar till att öka den taktiska effektiviteten förstådd somverkanseffektivitet, kostnadseffektivitet, logistisk effektivitet samt minskad oönskadsidoverkan. Kartläggningen sker genom en komparativ litteraturstudie medkompletterande expertintervjuer. Med hjälp av kurskorrigerande tändrör som medger nära precisionsbekämpning kanen rad vinster erhållas. Exempel på sådana vinster är minskad spridning samt ökaddimensionering av verkan, minskad risk för oönskad sidoverkan, en lägre totalkostnad för ammunition samt minskat behov av transporter genom ökad effekt av detenskilda skottet. / Sweden’s increased international commitment has altered the forms andenvironments of today's battlefield and military operations for units within theSwedish Armed Forces. First and foremost it means that all units have to be able tohandle all levels of conflict in most types of environments, including urban terrain.As a consequence of this, new needs and requirements arise concerning indirect fireand Artillery precision strike capabilities. The purpose of this thesis is to investigate if and to what extent a course correctingfuse contributes to an increased tactical efficiency within the areas of effect, cost,logistics and reduced risk of collateral damage. The investigation is made through acomparative literature study with supplementary expert interviews.With the help of a course correcting fuse, which allows for close precision capability,a series of achievements can be acquired. Examples of such achievements are reduced dispersion and increased capability ofdimensioning of effects, reduced risk of collateral damage, lower total cost ofmunitions and reduced demand of logistics.

Thesis (M.Tech.: Electronic Engineering)-Dept. of Electronic Engineering, Durban University of Technology, 2007. 1 v. (various pagings) / The objective was to develop a turbo code demonstration system for educational use. The aim was to build a system that would execute rapidly and produce a graphical display exemplifying the power of turbo codes and showing the effects of parameter variation.

Approved for public release; distribution is unlimited / The IEEE 802.11a standard uses a coded orthogonal frequency division multi-plexing (COFDM) scheme in the 5-GHz band to support data rates up to 54 Mbps. The COFDM was chosen because of its robustness to multipath fading affects. In the stan-dard, convolutional codes are used for error correction. This thesis examines the perform-ance of the COFDM system with variable rate Reed-Muller (RM) error correction codes with a goal to reduce the peak-to-average power ratio (PAPR). Contrary to the expecta-tions, RM codes did not provide expected improvement in PAPR reduction. Peak clip-ping and Hanning windowing techniques were investigated in order to reduce the PAPR. The results indicate that a tradeoff exists between the PAPR and the bit-error rate (BER) performance. Although peak clipping yielded considerable reduction in PAPR, it required high signal-to-noise ratios. On the other hand, Hanning windowing provided only a small reduction in PAPR with reasonable BER performance. / Lieutenant Junior Grade, Turkish Navy

M.Ing. (Electrical and Electronic Engineering) / In this study, the problem of correcting burst of adjacent deletions by adapting product codes was investigated. The first step in any digital transmission is to establish synchronization between the sending and receiving nodes. This initial synchronization ensures that the receiver samples the information bits at the correct interval. Unfortunately synchronization is not guaranteed to last for the entire duration of data transmission. Though synchronization errors rarely occur, it has disastrous effects at the receiving end of transmission. These synchronization errors are modelled as either insertions or deletions in the transmitted data. In the best case scenario, these errors are restricted to single bit errors. In the worst case scenario, these errors lead to bursts of bits being incorrect. If these synchronization errors are not detected and corrected, it can cause a shift in the transmitted sequence which in turn leads to loss of synchronization. When a signal is subjected to synchronization errors it is difficult accurately recover the original data signal. In addition to the loss of synchronization, the information transmitted over the channel is also subjected to noise. This noise in the channel causes inversion errors within the signal. The objective of this dissertation is to investigate if an error correction scheme can be designed that has the ability to detect and correct adjacent bursts of deletions and random inversion errors. This error correction scheme needed to make use of a product code matrix structure. This product matrix needed to incorporate both an error correction and synchronization technique. The chosen error correcting techniques were Hamming and Reed-Solomon codes. The chosen synchronization techniques for this project were the marker technique or an adaptation of the Hamming code technique. In order to find an effective model, combinations of these models were simulated and compared. From the research obtained and analyzed in this document it was found that, depending on the desired performance, complexity and code rate, an error correction scheme can be used in the efficient correction of bursts of adjacent deletions by adapting product codes.

Les code en métrique rang attirent l’attention depuis quelques années en raison de leur application possible au codage réseau linéaire aléatoire (random linear network coding), à la cryptographie à clé publique, au codage espace-temps et aux systèmes de stockage distribué. Une construction de codes algébriques en métrique rang de cardinalité optimale a été introduite par Delsarte, Gabidulin et Roth il y a quelques décennies. Ces codes sont considérés comme l’équivalent des codes de Reed – Solomon et ils sont basés sur l’évaluation de polynômes linéarisés. Ils sont maintenant appelés les codes de Gabidulin. Cette thèse traite des codes en bloc et des codes convolutifs en métrique rang avec l’objectif de développer et d’étudier des algorithmes de décodage efficaces pour ces deux classes de codes. Après une introduction dans le chapitre 1, le chapitre 2 fournit une introduction rapide aux codes en métrique rang et leurs propriétés. Dans le chapitre 3, on considère des approches efficaces pour décoder les codes de Gabidulin. Lapremière partie de ce chapitre traite des algorithmes rapides pour les opérations sur les polynômes linéarisés. La deuxième partie de ce chapitre résume tout d’abord les techniques connues pour le décodage jusqu’à la moitié de la distance rang minimale (bounded minimum distance decoding) des codes de Gabidulin, qui sont basées sur les syndromes et sur la résolution d’une équation clé. Ensuite, nous présentons et nous prouvons un nouvel algorithme efficace pour le décodage jusqu’à la moitié de la distance minimale des codes de Gabidulin. Le chapitre 4 est consacré aux codes de Gabidulin entrelacés et à leur décodage au-delà de la moitié de la distance rang minimale. Dans ce chapitre, nous décrivons d’abord les deux approches connues pour le décodage unique et nous tirons une relation entre eux et leurs probabilités de défaillance. Ensuite, nous présentons un nouvel algorithme de décodage des codes de Gabidulin entrelacés basé sur l’interpolation des polynômes linéarisés. Nous prouvons la justesse de ses deux étapes principales — l’interpolation et la recherche des racines — et montrons que chacune d’elles peut être effectuée en résolvant un système d’équations linéaires. Jusqu’à présent, aucun algorithme de décodage en liste en temps polynomial pour les codes de Gabidulin n’est connu et en fait il n’est même pas clair que cela soit possible. Cela nous a motivé à étudier, dans le chapitre 5, les possibilités du décodage en liste en temps polynomial des codes en métrique rang. Cette analyse est effectuée par le calcul de bornes sur la taille de la liste des codes en métriques rang en général et des codes de Gabidulin en particulier. Étonnamment, les trois nouvelles bornes révèlent toutes un comportement des codes en métrique rang qui est complètement différent de celui des codes en métrique de Hamming. Enfin, dans le chapitre 6, on introduit des codes convolutifs en métrique rang. Ce qui nous motive à considérer ces codes est le codage réseau linéaire aléatoire multi-shot, où le réseau inconnu varie avec le temps et est utilisé plusieurs fois. Les codes convolutifs créent des dépendances entre les utilisations différentes du réseau aun de se adapter aux canaux difficiles. Basé sur des codes en bloc en métrique rang (en particulier les codes de Gabidulin), nous donnons deux constructions explicites des codes convolutifs en métrique rang. Les codes en bloc sous-jacents nous permettent de développer un algorithme de décodage des erreurs et des effacements efficace pour la deuxième construction, qui garantit de corriger toutes les séquences d’erreurs de poids rang jusqu’à la moitié de la distance rang active des lignes. Un résumé et un aperçu des problèmes futurs de recherche sont donnés à la fin de chaque chapitre. Finalement, le chapitre 7 conclut cette thèse. / Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed–Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed–Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code.