Some demonstrative embodiments include apparatuses, devices, systems and methods of communicating a Physical Layer Protocol Data Unit (PPDU). For example, an Enhanced Directional Multi-Gigabit (DMG) (EDMG) station (STA) may be configured to encode a Physical Layer (PHY) Service Data Unit (PSDU) of at least one user in an EDMG PHY Protocol Data Unit (PPDU) according to an EDMG Low-Density Parity-Check (LDPC) encoding scheme, which is based at least on a count of one or more spatial streams for transmission to the user; and transmit the EDMG PPDU in a transmission over a channel bandwidth in a frequency band above 45 Gigahertz (GHz).