Systems and methodologies are described that facilitate transmitting beacon symbols of a beacon message such that a sequence of symbols can satisfy a linear constraint over a field where the field elements can be identified with carriers. In this regard, a coding scheme can be applied to a beacon message; the coding scheme can produce a plurality of beacon symbols to transmit on given subcarriers. A receiving device of the beacon symbols can decode a beacon message by receiving less than the total number of symbols in a beacon message and determining the remaining symbol subcarriers based on the linear constraint. Thus, more efficient decoding of beacons is facilitated as well as resolving beacon ambiguity by figuring out which symbols satisfy linear constraints for the symbols, and resolving time and frequency shift by detecting an offset that would result in satisfaction of the linear constraint.