  Availability of abundant spectrum has enabled millimeter wave (mm-wave) as a
prominent candidate solution for the next generation cellular networks. Highly
directional transmissions are essential for exploitation of mm-wave bands to
compensate high propagation loss and attenuation. The directional transmission,
nevertheless, necessitates a specific design for mm-wave initial cell
discovery, as conventional omni-directional broadcast signaling may fail in
delivering the cell discovery information. To address this issue, this paper
provides an analytical framework for mm-wave beamformed cell discovery based on
an information theoretical approach. Design options are compared considering
four fundamental and representative broadcast signaling schemes to evaluate
discovery latency and signaling overhead. The schemes are then simulated under
realistic system parameters. Analytical and simulation results reveals four key
findings: (i) For cell discovery without knowledge of beacon timing,
analog/hybrid beamforming performs as well as digital beamforming in terms of
cell discovery latency; (ii) Single beam exhaustive scan optimize the latency,
however leads to overhead penalty; (iii) Multi-beam simultaneous scan can
significantly reduce the overhead, and provide the flexibility to achieve
trade-off between the latency and the overhead; (iv) The latency and the
overhead are relatively insensitive to extreme low block error rates.
