TY - JOUR
T1 - Heuristic Solution of a Signal Design Optimization Problem
AU - Kernighan, B. W.
AU - Lin, S.
PY - 1973/9
Y1 - 1973/9
N2 - This paper discusses a heuristic solution procedure for a combinatorial optimization problem that originates in designing signal constellations for modems. The design problem is to place m signals in a two‐dimensional space to minimize the average error rate under specified noise conditions, using a maximum‐likelihood decoding scheme. Intuitively, it amounts (roughly) to spreading the signal points as far apart as possible, according to the distance measurement implied by the noise function. We show how this problem can be reduced to a discrete one: Given an ℓ by n matrix P, and m < ℓ, find an m‐row subset M = {i1, ···, im} of the rows of P that maximizes (Formula Presented.) and then describe an efficient procedure for finding this maximizing set. Experiments indicate that the procedure is a useful tool, both for analysis of existing and proposed signal constellations and for finding new, near‐optimum ones.
AB - This paper discusses a heuristic solution procedure for a combinatorial optimization problem that originates in designing signal constellations for modems. The design problem is to place m signals in a two‐dimensional space to minimize the average error rate under specified noise conditions, using a maximum‐likelihood decoding scheme. Intuitively, it amounts (roughly) to spreading the signal points as far apart as possible, according to the distance measurement implied by the noise function. We show how this problem can be reduced to a discrete one: Given an ℓ by n matrix P, and m < ℓ, find an m‐row subset M = {i1, ···, im} of the rows of P that maximizes (Formula Presented.) and then describe an efficient procedure for finding this maximizing set. Experiments indicate that the procedure is a useful tool, both for analysis of existing and proposed signal constellations and for finding new, near‐optimum ones.
UR - http://www.scopus.com/inward/record.url?scp=0015665925&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0015665925&partnerID=8YFLogxK
U2 - 10.1002/j.1538-7305.1973.tb02009.x
DO - 10.1002/j.1538-7305.1973.tb02009.x
M3 - Article
AN - SCOPUS:0015665925
SN - 0005-8580
VL - 52
SP - 1145
EP - 1159
JO - Bell System Technical Journal
JF - Bell System Technical Journal
IS - 7
ER -