International Telemetering Conference Proceedings / October 28-31, 1996 / Town and Country Hotel and Convention Center, San Diego, California / This paper describes a 300 Mega Bit Per Second (MBPS) Front End Processor (FEP) prototype completed in early 1993. The FEP implements a patent pending parallel frame synchronizer (frame sync) design in 12 Actel 1240 Field Programmable Gate Arrays (FPGA's). The FEP also provides (255,223) Reed-Solomon (RS) decoding and a High Performance Parallel Interface (HIPPI) output interface. The recent introduction of large RAM based FPGA's allows greater high speed data processing integration and flexibility to be achieved. A proposed FEP implementation based on Altera 10K50 FPGA's is described. This design can be implemented on a single slot 6U VME module, and includes a PCI Mezzanine Card (PMC) for a commercial Fibre Channel or Asynchronous Transfer Mode (ATM) output interface module. Concepts for implementation of (255,223) RS and Landsat 7 Bose-Chaudhuri-Hocquenghem (BCH) decoding in FPGA's are also presented. The paper concludes with a summary of the advantages of high speed data processing in FPGA's over Application Specific Integrated Circuit (ASIC) based approaches. Other potential data processing applications are also discussed.

Je traite du décodage de deux grandes familles de codes algébriques :<br />les codes cycliques binaires et les codes de Reed-Solomon sur un<br />alphabet $q$-aire (ainsi que les codes géométriques). En ce qui<br />concerne les codes cycliques, ceux-ci n'ont pas d'algorithme générique<br />de décodage, mis à part les codes BCH ou assimilés (bornes de<br />Hartman-Tzeng, de Roos). Au premier rang des codes intéressants pour<br />lesquels on ne connaît pas d'algorithme de décodage {\em générique}<br />figurent les {\em codes à résidus quadratiques}, qui ont de bons<br />paramètres. J'étudie une mise en équation du problème du décodage par<br />syndrôme de ces codes, que l'on peut résoudre avec des outils de base<br />de Gröbner. On obtient ainsi des algorithmes de décodage de complexité<br />raisonnable pour ces codes. Ces travaux ont fait l'objet d'une partie<br />de la thèse de Magali Bardet.<br /><br /><br />En ce qui concerne les codes de Reed-Solomon, ceux-ci peuvent être vus<br />comme des {\em codes d'évaluation}, et le problème de décodage associé<br />revient à approcher une fonction par des polynômes de base degré. De<br />grands progrès ont été réalisés par Guruswami et Sudan, qui ont trouvé<br />un algorithme qui décode bien au delà des rayons classiques de<br />décodage, en relaxant l'hypothèse que la solution doit être unique. Je<br />propose d'améliorer certaines étapes de cet algorithme, en le rendant<br />plus rapide et déterministe (notamment en évitant une factorisation de<br />polynôme sur un corps fini), dans le cas des codes Reed-Solomon, et<br />dans le cas des codes géométriques. Ces travaux ont été effectués en<br />encadrant Lancelot Pecquet.<br /><br />Du point de vue théorique, j'ai étudié des généralisations<br />multivariées, qui correspondent à certains codes: les codes produits<br />de Reed-Solomon, et les codes de Reed-Muller. On obtient ainsi un bon<br />rayon de décodage, dans le cas des codes de petit taux. Dans le cas de<br />codes de Reed-Muller sur l'alphabet binaire, Cédric Tavernier, dans sa<br />thèse sous ma direction, a produit et implanté un algorithme efficace,<br />plus que ceux basés sur l'algorithme de Guruswami-Sudan.<br /><br /><br /><br />J'ai étudié les aspects négatifs du problème de décodage par syndrôme<br />des codes linéaires, et du décodage des codes de Reed-Solomon, quand<br />le nombre d'erreurs est élevé, en but d'application en cryptographie.<br />Dans le premier cas, j'ai construit une fonction de hachage<br />cryptographique à réduction de sécurité, c'est-à-dire que trouver une<br />faiblesse dans le fonction de hachage revient à résoudre un problème<br />réputé difficile de codage. J'ai aussi construit une nouvelle<br />primitive de chiffrement à clé publique, reposant sur la difficulté de<br />décoder les codes de Reed-Solomon.<br /><br />Dans un domaine plus appliqué, j'ai proposé avec Raghav Bhaskar un<br />nouvel algorithme d'échange de clé multi-utilisateurs, fondé sur le<br />problème du logarithme discret. Raghav Bhaskar a fourni une preuve de<br />sécurité de ce protocole, pendant sa thèse sous ma direction. Nous<br />avons aussi étudié comment adapter ce protocole aux pertes de<br />messages, car notre protocole est un des seuls qui est robuste à ces<br />pertes.

This thesis describes barcodes which are used in postal services. Specifically, it is concerned with Intelligent Mail Barcode, the GS1-128 code, the C128 code of Ceska posta (Czech Postal Services) and the QR code. The thesis attempts to analyze methods of encoding information into barcodes and error detection algorithms used for error correction during the decoding processes. Most importantly, there is described Reed-Solomon error correction in the QR code. There are presented and evaluated different methods of code detecting which are suggested by authors of various academic articles. The thesis also describes the method of creating test sets of images and proposed appearances of the scanning scene. Additionally, there are described algorithms for detection and decoding barcodes GS1-128, C128 and IMB in the image which was created during the work on this thesis. Finally, there is the evaluation of the percentage success of algorithms.

The doctoral thesis deals with design of coding for frequency hopping stations in band with intensive jamming. In digital modulations erroneous determination of the modulation state occurs due to jam at the receiver side. The result is erroneously transferred symbols of the message. Errors created during the transmission can be eliminated by using error control systems. It is also possible to prevent these errors by using algorithms (techniques) of frequency hopping which select the appropriate channel. Appropriate communication channel is a channel with a lower probability of erroneous symbol in the message. The main contribution of this thesis is to design a new frequency hopping technique with collision avoidance (FH/CA). The station with FH/CA technique measures signal levels in the considered several channels before every jump. Based on the measurements the most appropriate channel with the lowest value of measured signal level is selected. Therefore, it is more probable that a jump to an unoccupied channel with a transmission will occur. Using a mathematical model, the performance of the newly proposed FH/CA technique is compared with the currently used techniques FH and AFH. Comparison criteria are the probability of a collision between an FH/CA communication system and a static (device transmitting continuously at a fixed frequency) or dynamic jammer (i.e. other FH or AFH systems). By comparing the values of the probability of jammed transmission, indisputable theoretical advantages of the new FH/CA technique were found, compared to the currently used FH and AFH techniques. The FH/CA technique always has better or equal results compared with the FH technique in the case of interference by static and dynamic jammers. The FH/CA technique in a band with static and dynamic jammers usually has better results than the AFH technique. A significant contribution of the FH/CA technique can be seen in the case of dynamic jammers. On the other hand, in the case of static jammers the FH/CA technique is in certain situations worse than the AFH technique. The accuracy of the mathematical models were successfully verified on a simulation model that was created as a part of this thesis in the MATLAB environment. Based on the obtained data from the model there was designed coding for frequency hopping stations with the new technique of frequency hopping FH/CA which is designed for small-volume data transfer in a band with intensive jamming.