A binary walking robot moves as a result of bi-state actuator transitions. Because of the bi-state nature of binary joints, many research results about continuous walking robots cannot be applied to binary walking robots directly. In this paper, a new and simple model of rigid-link binary walking robot is proposed, around which related concepts are introduced, and formulas are derived. Based on this model, general characteristics and limitations of periodic gaits are discussed, and the stability qualities of several straight-line walking periodic gaits are studied in both pitch-greater-than-stroke and stroke-greater-than-pitch cases. Valuable results are obtained from the analysis, which should be followed in the design of rigid-link binary walking robots.