Techniques for generating a synchronization signal (e.g., a secondary synchronization signal) based on an M-sequence are described. In one design, first and second sequences for a secondary synchronization signal may be generated based on different cyclic shifts of the M-sequence. The cyclic shifts may be determined based on cell ID and/or other information to send in the secondary synchronization signal. An output sequence may be generated based on the first and second sequences, e.g., by combining the first and second sequences and scrambling the combined first and second sequences with at least one scrambling sequence. The secondary synchronization signal may then be generated based on the output sequence, e.g., by mapping samples in the output sequence to subcarriers and generating an OFDM symbol with the mapped samples. Detection for the secondary synchronization signal may be efficiently performed using fast M-sequence transform (FMT).