For example, an Enhanced Directional Multi-Gigabit (DMG) (EDMG) wireless communication station (STA) may be configured to scramble, according to a first scrambling sequence, a plurality of EDMG Header B bits of an EDMG Header B field of an EDMG Multi-User (MU) Physical Layer (PHY) Protocol Data Unit (PPDU) into a plurality of scrambled header bits; generate a Low-Density Parity-Check (LDPC) codeword based on the plurality of scrambled header bits; determine a data block based on the LDPC codeword; generate one or more scrambled data blocks based on the data block by scrambling the data block according to a second scrambling sequence; and transmit a wireless transmission of the EDMG Header B based on the one or more scrambled data blocks.