The first frame of a paging slot (405) contains a portion of every page's (401-404) address. Likewise, the second, third, and fourth frames of the slot (405) contain a second, third, and fourth portion from each of the paging addresses. Address information is organized in the atomic frames of the slot (405) in such a way that the information in the earliest frame gives the mobile a high probability that it can determine that no messages directed to it are present in the slot. After receiving a first frame, a mobile station uses known partial address comparison techniques to determine if the mobile station has a page pending.