Change search
Link to record
Permanent link

Direct link
BETA
Laksman, Efraim
Publications (3 of 3) Show all publications
Laksman, E., Lennerstad, H. & Nilsson, M. (2015). Generalized upper bounds on the minimum distance of PSK block codes. IMA Journal of Mathematical Control and Information, 32(2), 305-327
Open this publication in new window or tab >>Generalized upper bounds on the minimum distance of PSK block codes
2015 (English)In: IMA Journal of Mathematical Control and Information, ISSN 0265-0754, E-ISSN 1471-6887, Vol. 32, no 2, p. 305-327Article, review/survey (Refereed) Published
Abstract [en]

This paper generalizes previous optimal upper bounds on the minimum Euclidean distance for phase shift keying (PSK) block codes, that are explicit in three parameters: alphabet size, block length and code size. The bounds are primarily generalized from codes over symmetric PSK to codes over asymmetric PSK and also to general alphabet size. Furthermore, block codes are optimized in the presence of other types of noise than Gaussian, which induces also non-Euclidean distance measures. In some instances, codes over asymmetric PSK prove to give higher Euclidean distance than any code over symmetric PSK with the same parameters. We also provide certain classes of codes that are optimal among codes over symmetric PSK.

Abstract [sv]

Detta papper generaliserar tidigare optimala övre gränser för minimala Euklidiska avståndet för fasskift block koder, s.k. phase shift keying (PSK). De är explicita i tre parametrar: alfabetstorlek, blocklängd och kodstorlek. Gränserna är framförallt generaliserade från koder över symmetrisk PSK till koder över asymmetrisk PSK men även till generell alfabetsstorlek. Block koder är även generaliserade i närvaro av annat brus än gaussiskt, vilket leder till icke-Euklidiska avståndsmått. I vissa fall ger asymmetrisk PSK högre Euklidiskt avstånd än symmetriskt med samma parametrar. Vi visar också att vissa kodklasser är optimala i gruppen av symmetrisk PSK.

Place, publisher, year, edition, pages
Oxford Journals, 2015
Keywords
Assymetric PSK, symmetric PSK, Elias' bound.
National Category
Mathematical Analysis Telecommunications
Identifiers
urn:nbn:se:bth-6608 (URN)10.1093/imamci/dnt047 (DOI)000358779200006 ()oai:bth.se:forskinfo7520A9E3949B10C1C1257D630059B28A (Local ID)oai:bth.se:forskinfo7520A9E3949B10C1C1257D630059B28A (Archive number)oai:bth.se:forskinfo7520A9E3949B10C1C1257D630059B28A (OAI)
Note

Open access article

Available from: 2014-10-03 Created: 2014-09-30 Last updated: 2017-12-04Bibliographically approved
Laksman, E. (2012). Combinatorial Optimization: Three Applications. (Doctoral dissertation). Karlskrona: Blekinge Institute of Technology
Open this publication in new window or tab >>Combinatorial Optimization: Three Applications
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Combinatorial optimization is a diverse area of mathematics. It concerns optimization on feasible regions defined by discrete sets, graphs, hypergraphs, matroids, etc. . . which all have a large number of applications. They occur in virtually all domains of human activity since humans always want to do things easier, faster, consume less resources, etc. . . This thesis concerns three applied problems within combinatorial optimization. The first paper generalizes previous optimal upper bounds on the minimum Euclidean distance for phase-shift keying (PSK) block codes, that are explicit in the parameters alphabet size, block length and code size. There is a strong connection between high minimum Euclidean distance and good error-correcting capabilities. The bounds are generalized in several respects, such as from codes on symmetric PSK to codes on asymmetric PSK. They are also generalized to other types of noise than Gaussian, allowing more efficient block codes when noise is non-Gaussian. We provide examples of codes on asymmetric PSK that have higher minimum Euclidean distance than any comparable codes on symmetric PSK.Several classes of codes are shown to be optimal among codes on symmetric PSK since their Euclidean distance coincides with the bound. The second paper considers a parallel computer system with m identical computers,where we study optimal performance precaution for one possible computer crash. We anticipate that some computer may crash, and restrict the cost in such a situation. How costly is such a precaution when no crash occurs? We set a restriction that the completion time of a parallel program after a crash is at most a factor r + 1 larger than if we use an optimal allocation with m - 1 computers. This is an r-dependent restriction of the set of allocations of a program. Then the worst-case ratio of the optimal r-dependent completion time in the case of no crash and the unrestricted optimal completion time defines a function f(r,m). In the paper we establish upper and lower bounds of the worst-case cost function f(r,m) and characterize worst-case programs. The third paper considers the problem of Map Matching (MM), i.e. matching time and location measurements of a vehicle to a route in a road network. The paper presents a probabilistic algorithm for MM based on a second order hidden Markov model (HMM), as opposed to first order HMMs which are usually used. This allows a more detailed analysis of the data while preserving algorithmic complexity O(n). Both measurement densities and transition probabilities are determined with respect to Kolmogorov's third axiom, which in this context implies that the probabilities are additive over a partition of a road segment.

Place, publisher, year, edition, pages
Karlskrona: Blekinge Institute of Technology, 2012
Series
Blekinge Institute of Technology Doctoral Dissertation Series, ISSN 1653-2090 ; 10
National Category
Mathematical Analysis
Identifiers
urn:nbn:se:bth-00538 (URN)oai:bth.se:forskinfoBF9F1C6CE7BA0513C1257A8B00523D3A (Local ID)oai:bth.se:forskinfoBF9F1C6CE7BA0513C1257A8B00523D3A (Archive number)oai:bth.se:forskinfoBF9F1C6CE7BA0513C1257A8B00523D3A (OAI)
External cooperation:
Available from: 2012-10-31 Created: 2012-10-02 Last updated: 2016-09-06Bibliographically approved
Laksman, E., Lennerstad, H. & Lundberg, L. (2012). Optimal computer crash performance precaution. Discrete Mathematics and Theoretical Computer Science, 14(1), 55-68
Open this publication in new window or tab >>Optimal computer crash performance precaution
2012 (English)In: Discrete Mathematics and Theoretical Computer Science, ISSN 1462-7264, Vol. 14, no 1, p. 55-68Article in journal (Refereed) Published
Abstract [en]

For a parallel computer system withmidentical computers, we study optimal performance precaution for one possible computer crash. We want to calculate the cost of crash precaution in the case of no crash. We thus define a tolerance level r meaning that we only tolerate that the completion time of a parallel program after a crash is at most a factor r + 1 larger than if we use optimal allocation on m - 1 computers. This is an r-dependent restriction of the set of allocations of a program. Then, what is the worst-case ratio of the optimal r-dependent completion time in the case of no crash and the unrestricted optimal completion time of the same parallel program? We denote the maximal ratio of completion times f(r, m) - i.e., the ratio for worst-case programs. In the paper we establish upper and lower bounds of the worst-case cost function f(r, m) and characterize worst-case programs.

Place, publisher, year, edition, pages
Maison de l'informatique et des mathematiques discretes, 2012
Keywords
Computer crash, Load balancing, Optimization, Parallel computer, Process allocation, Scheduling
National Category
Mathematics Computer Sciences
Identifiers
urn:nbn:se:bth-7056 (URN)oai:bth.se:forskinfoB06EE51C5781B5C7C1257AC90038EBEF (Local ID)oai:bth.se:forskinfoB06EE51C5781B5C7C1257AC90038EBEF (Archive number)oai:bth.se:forskinfoB06EE51C5781B5C7C1257AC90038EBEF (OAI)
Note
Open Access JournalAvailable from: 2012-12-21 Created: 2012-12-03 Last updated: 2018-01-11Bibliographically approved
Organisations

Search in DiVA

Show all publications