Recent studies suggest that spectrum congestion is primarily due to inefficient spectrum usage rather than spectrum availability. Dynamic spectrum access (DSA) and cognitive radio (CR) are two techniques being considered to improve spectrum efficiency and utilization. The advent of CR has created a paradigm shift in wireless communications and instigated a change in FCC policy towards spectrum regulations. Within the hierarchical DSA model, spectrum overlay and underlay techniques are employed to enable primary and secondary users to coexist while improving overall spectrum efficiency. As employed here, spectrum overlay exploits unused (white) spectral regions while spectrum underlay exploits underused (gray) spectral regions. In general, underlay approaches use more spectrum than overlay approaches and operate below the noise floor of primary users. Spectrally modulated, spectrally encoded (SMSE) signals, to include orthogonal frequency domain multiplexing (OFDM) and multi-carrier code division multiple access (MC-CDMA), are candidate CR waveforms. The SMSE structure supports and is well suited for CR-based software defined radio (SDR) applications. This paper provides a general soft decision SMSE (SDSMSE) framework that extends the original SMSE framework to achieve synergistic CR benefits of overlay and underlay techniques. This extended framework provides considerable flexibility to design overlay, underlay and hybrid overlay/underlay waveforms that are scenario dependent. Overlay/underlay framework flexibility is demonstrated herein for a family of SMSE signals, including OFDM and MC-CDMA. Analytic derivation of CR error probability for overlay and underlay applications is presented. Simulated performance analysis of overlay, underlay and hybrid overlay/underlay waveforms is also presented and benefits discussed, to include improved spectrum efficiency and channel capacity maximization. Performance analysis of overlay/underlay CR waveform in fading channels will be discussed in Part II of the paper.