Analysis of permutation distance-preserving mappings using graphs
- Swart, Theo G., Ferreira, Hendrik C.
- Authors: Swart, Theo G. , Ferreira, Hendrik C.
- Date: 2007
- Subjects: Mappings (Mathematics) , Permutations , Representations of graphs
- Language: English
- Type: Conference proceedings
- Identifier: http://hdl.handle.net/10210/15518 , uj:15670 , Citation: Swart, T.G. & Ferreira, H.C. 2007. Analysis of permutation distance-preserving mappings using graphs. In: Proceedings of the International Symposium on Communication Theory and its Applications, Ambleside, England, July 16-20, 2007
- Description: Abstract A new way of analyzing permutation distance preserving mappings is presented by making use of a graph representation. The properties necessary to make such graphs distance-preserving and how this relates to the total sum of distances that exist for such mappings, are investigated. This new knowledge is used to analyze previous constructions, as well as showing the existence or non-existence of simple algorithms for mappings attaining the upper bound on the sum of distances. Finally, two applications for such graphs are considered.
- Full Text:
- Authors: Swart, Theo G. , Ferreira, Hendrik C.
- Date: 2007
- Subjects: Mappings (Mathematics) , Permutations , Representations of graphs
- Language: English
- Type: Conference proceedings
- Identifier: http://hdl.handle.net/10210/15518 , uj:15670 , Citation: Swart, T.G. & Ferreira, H.C. 2007. Analysis of permutation distance-preserving mappings using graphs. In: Proceedings of the International Symposium on Communication Theory and its Applications, Ambleside, England, July 16-20, 2007
- Description: Abstract A new way of analyzing permutation distance preserving mappings is presented by making use of a graph representation. The properties necessary to make such graphs distance-preserving and how this relates to the total sum of distances that exist for such mappings, are investigated. This new knowledge is used to analyze previous constructions, as well as showing the existence or non-existence of simple algorithms for mappings attaining the upper bound on the sum of distances. Finally, two applications for such graphs are considered.
- Full Text:
Synchronization with permutation codes and Reed-Solomon codes
- Authors: Shongwe, Thokozani Calvin
- Date: 2014-09-23
- Subjects: Coding theory , Synchronization , Data transmission systems , Reed-Solomon codes , Permutations
- Type: Thesis
- Identifier: http://ujcontent.uj.ac.za8080/10210/386508 , uj:12373 , http://hdl.handle.net/10210/12157
- Description: D.Ing. (Electrical And Electronic Engineering) , We address the issue of synchronization, using sync-words (or markers), for encoded data. We focus on data that is encoded using permutation codes or Reed-Solomon codes. For each type of code (permutation code and Reed-Solomon code) we give a synchronization procedure or algorithm such that synchronization is improved compared to when the procedure is not employed. The gure of merit for judging the performance is probability of synchronization (acquisition). The word acquisition is used to indicate that a sync-word is acquired or found in the right place in a frame. A new synchronization procedure for permutation codes is presented. This procedure is about nding sync-words that can be used speci cally with permutation codes, such that acceptable synchronization performance is possible even under channels with frequency selective fading/jamming, such as the power line communication channel. Our new procedure is tested with permutation codes known as distance-preserving mappings (DPMs). DPMs were chosen because they have de ned encoding and decoding procedures. Another new procedure for avoiding symbols in Reed-Solomon codes is presented. We call the procedure symbol avoidance. The symbol avoidance procedure is then used to improve the synchronization performance of Reed-Solomon codes, where known binary sync-words are used for synchronization. We give performance comparison results, in terms of probability of synchronization, where we compare Reed-Solomon with and without symbol avoidance applied.
- Full Text:
- Authors: Shongwe, Thokozani Calvin
- Date: 2014-09-23
- Subjects: Coding theory , Synchronization , Data transmission systems , Reed-Solomon codes , Permutations
- Type: Thesis
- Identifier: http://ujcontent.uj.ac.za8080/10210/386508 , uj:12373 , http://hdl.handle.net/10210/12157
- Description: D.Ing. (Electrical And Electronic Engineering) , We address the issue of synchronization, using sync-words (or markers), for encoded data. We focus on data that is encoded using permutation codes or Reed-Solomon codes. For each type of code (permutation code and Reed-Solomon code) we give a synchronization procedure or algorithm such that synchronization is improved compared to when the procedure is not employed. The gure of merit for judging the performance is probability of synchronization (acquisition). The word acquisition is used to indicate that a sync-word is acquired or found in the right place in a frame. A new synchronization procedure for permutation codes is presented. This procedure is about nding sync-words that can be used speci cally with permutation codes, such that acceptable synchronization performance is possible even under channels with frequency selective fading/jamming, such as the power line communication channel. Our new procedure is tested with permutation codes known as distance-preserving mappings (DPMs). DPMs were chosen because they have de ned encoding and decoding procedures. Another new procedure for avoiding symbols in Reed-Solomon codes is presented. We call the procedure symbol avoidance. The symbol avoidance procedure is then used to improve the synchronization performance of Reed-Solomon codes, where known binary sync-words are used for synchronization. We give performance comparison results, in terms of probability of synchronization, where we compare Reed-Solomon with and without symbol avoidance applied.
- Full Text:
Spectral shaping and distance mapping with permutation sequences
- Authors: Ouahada, Khmaies Taher
- Date: 2012-06-04
- Subjects: Mappings (Mathematics) , Error-correcting codes (Information theory) , Permutations
- Type: Thesis
- Identifier: uj:2344 , http://hdl.handle.net/10210/4800
- Description: D.Ing. , In this thesis we combined two techniques, namely a spectral shaping technique and a distance-preserving mapping technique to design new codes with both special spectrum shaping and error correction capabilities, in order to overcome certain communication problems like those that occur in a power-line communication channel. A new distance-preserving mapping construction based on graph theory is firstly presented. The k-cube graph construction from binary sequences to permutation sequences reached the upper bound on the sum of the Hamming distances for certain lengths of the permutation sequences and achieves the same sum of the Hamming distances as the best previously published constructions for most of the rest of the lengths. The k-cube graph construction is considered to be a simple and easy construction to understand the concept of mappings and especially the concept of a distance-reducing mapping.
- Full Text:
- Authors: Ouahada, Khmaies Taher
- Date: 2012-06-04
- Subjects: Mappings (Mathematics) , Error-correcting codes (Information theory) , Permutations
- Type: Thesis
- Identifier: uj:2344 , http://hdl.handle.net/10210/4800
- Description: D.Ing. , In this thesis we combined two techniques, namely a spectral shaping technique and a distance-preserving mapping technique to design new codes with both special spectrum shaping and error correction capabilities, in order to overcome certain communication problems like those that occur in a power-line communication channel. A new distance-preserving mapping construction based on graph theory is firstly presented. The k-cube graph construction from binary sequences to permutation sequences reached the upper bound on the sum of the Hamming distances for certain lengths of the permutation sequences and achieves the same sum of the Hamming distances as the best previously published constructions for most of the rest of the lengths. The k-cube graph construction is considered to be a simple and easy construction to understand the concept of mappings and especially the concept of a distance-reducing mapping.
- Full Text:
Concatenated permutation codes to correct substitution, deletion or transposition errors
- Authors: Heymann, Reolyn
- Date: 2016
- Subjects: Error-correcting codes (Information theory) , Permutations , Coding theory , Synchronization
- Language: English
- Type: Doctoral (Thesis)
- Identifier: http://hdl.handle.net/10210/84471 , uj:19224
- Description: Abstract: Abstract: Please refer to full text to view abstract , D.Ing. (Electrical and Electronic Engineering)
- Full Text:
- Authors: Heymann, Reolyn
- Date: 2016
- Subjects: Error-correcting codes (Information theory) , Permutations , Coding theory , Synchronization
- Language: English
- Type: Doctoral (Thesis)
- Identifier: http://hdl.handle.net/10210/84471 , uj:19224
- Description: Abstract: Abstract: Please refer to full text to view abstract , D.Ing. (Electrical and Electronic Engineering)
- Full Text:
Distance-preserving mappings and trellis codes with permutation sequences
- Authors: Swart, Theo G.
- Date: 2008-06-27T09:30:19Z
- Subjects: Mapping (Mathematics) , Error-correcting codes (Information theory) , Trellis-coded modulation , Permutations
- Type: Thesis
- Identifier: uj:10062 , http://hdl.handle.net/10210/744
- Description: Our research is focused on mapping binary sequences to permutation sequences. It is established that an upper bound on the sum of the Hamming distance for all mappings exists, and this sum is used as a criterion to ascertain how good previously known mappings are. We further make use of permutation trellis codes to investigate the performance of certain permutation mappings in a power-line communications system, where background noise, narrow band noise and wide band noise are present. A new multilevel construction is presented next that maps binary sequences to permutation sequences, creating new mappings for which the sum of Hamming distances are greater than previous known mappings. It also proved that for certain lengths of sequences, the new construction can attain our new upper bound on the sum of Hamming distances. We further extend the multilevel construction by showing how it can be applied to other mappings, such as permutations with repeating symbols and mappings with nonbinary inputs. We also show that a subset of the new construction yields permutation sequences that are able to correct insertion and deletion errors as well. Finally, we show that long binary sequences, formed by concatenating the columns of binary permutation matrices, are subsets of the Levenshtein insertion/deletion correcting codes. , Prof. H. C. Ferreira
- Full Text:
- Authors: Swart, Theo G.
- Date: 2008-06-27T09:30:19Z
- Subjects: Mapping (Mathematics) , Error-correcting codes (Information theory) , Trellis-coded modulation , Permutations
- Type: Thesis
- Identifier: uj:10062 , http://hdl.handle.net/10210/744
- Description: Our research is focused on mapping binary sequences to permutation sequences. It is established that an upper bound on the sum of the Hamming distance for all mappings exists, and this sum is used as a criterion to ascertain how good previously known mappings are. We further make use of permutation trellis codes to investigate the performance of certain permutation mappings in a power-line communications system, where background noise, narrow band noise and wide band noise are present. A new multilevel construction is presented next that maps binary sequences to permutation sequences, creating new mappings for which the sum of Hamming distances are greater than previous known mappings. It also proved that for certain lengths of sequences, the new construction can attain our new upper bound on the sum of Hamming distances. We further extend the multilevel construction by showing how it can be applied to other mappings, such as permutations with repeating symbols and mappings with nonbinary inputs. We also show that a subset of the new construction yields permutation sequences that are able to correct insertion and deletion errors as well. Finally, we show that long binary sequences, formed by concatenating the columns of binary permutation matrices, are subsets of the Levenshtein insertion/deletion correcting codes. , Prof. H. C. Ferreira
- Full Text:
Using graphs for the analysis and construction of permutation distance-preserving mappings
- Swart, Theo G., Ferreira, Hendrik C., Ouahada, Khmaies
- Authors: Swart, Theo G. , Ferreira, Hendrik C. , Ouahada, Khmaies
- Date: 2008
- Subjects: Code construction , Distance-preserving mappings , Representation of graphs , Permutations , Mappings (Mathematics)
- Language: English
- Type: Article
- Identifier: http://hdl.handle.net/10210/20030 , uj:16060 , ISSN: 0018-9448 , Citation: Swart, T.G., Ferreira H.C. & Ouahada, K. 2008. Using graphs for the analysis and construction of permutation distance-preserving mappings. IEEE Transactions on Information Theory, 54(2):910-916.
- Description: Abstract: A new way of looking at permutation distance-preserving mappings (DPMs) is presented by making use of a graph representation. The properties necessary to make such a graph distance-preserving, are also investigated. Further, this new knowledge is used to analyze previous constructions, as well as to construct a new general mapping algorithm for a previous multilevel construction.
- Full Text:
- Authors: Swart, Theo G. , Ferreira, Hendrik C. , Ouahada, Khmaies
- Date: 2008
- Subjects: Code construction , Distance-preserving mappings , Representation of graphs , Permutations , Mappings (Mathematics)
- Language: English
- Type: Article
- Identifier: http://hdl.handle.net/10210/20030 , uj:16060 , ISSN: 0018-9448 , Citation: Swart, T.G., Ferreira H.C. & Ouahada, K. 2008. Using graphs for the analysis and construction of permutation distance-preserving mappings. IEEE Transactions on Information Theory, 54(2):910-916.
- Description: Abstract: A new way of looking at permutation distance-preserving mappings (DPMs) is presented by making use of a graph representation. The properties necessary to make such a graph distance-preserving, are also investigated. Further, this new knowledge is used to analyze previous constructions, as well as to construct a new general mapping algorithm for a previous multilevel construction.
- Full Text:
- «
- ‹
- 1
- ›
- »