Patent ID: 8634490

Claim:
A method of determining a transmitted vector (x) representing a plurality of symbols transmitted on a wireless medium by a wireless transmitter, said plurality of symbols belonging to an alphabet according to a modulation technique employed by said wireless transmitter, said method being performed in a wireless receiver, wherein said wireless receiver and said wireless transmitter form a multiple-input multiple-output (MIMO) system, said method comprising: receiving a received vector (y) representative of said transmitted vector (x); performing a plurality of searches to generate a corresponding plurality of estimates of said transmitted vector (x); providing, as a final estimate of said transmitted vector (x), a first estimate in said corresponding plurality of estimates that has the least cost, wherein each of said plurality of searches comprises: generating a random initial vector having a same size as said transmitted vector (x); creating a vector-neighborhood of said random initial vector; choosing, as a solution vector, a vector in said vector-neighborhood that has a least cost function as compared to other vectors in said vector-neighborhood; and repeating said creating and said choosing to respectively create corresponding vector-neighborhoods and to choose corresponding vectors as corresponding solution vectors till a stop criterion is reached, wherein the solution vector obtained by said repeating when said stop criterion is reached is set as a corresponding estimate of said corresponding plurality of estimates of said transmitted vector (x), wherein said performing performs only a subset of searches if a second estimate obtained at the end of said subset of searches has a cost less than a threshold cost, said subset of searches being contained in said plurality of searches, wherein said providing provides said second estimate obtained at the end of said subset of searches as said final estimate instead of said first estimate, wherein said threshold cost is different for each search in said subset of searches, said MIMO system being an under-determined system.