The present invention provides a preamble that is inserted into an OFDMA frame and has a common sequence for all the base stations participating in a transmission. The subscriber station performs fine synchronization using the common sequence on the common preamble, and the resulting peaks will provide the locations of candidate base stations. The base station specific search is then performed in the vicinities of those peaks by using base station specific pseudo-noise sequences. With this two stage cell search, the searching window is drastically reduced. The preamble is matched to known values by a respective receiver to decode the signals and permit multiple signals to be transferred from the transmitter to the receiver. The preamble may comprise two parts, Preamble-1 and Preamble-2, which may be used in different systems, including multioutput, multi-input (MIMO) systems.