Recently, rehabilitation treadmills are designed for helping injured persons such as stroke patients and injury athletes in the process of physical therapy. By monitoring the changes of paces and gaits, one can estimate the progress of rehabilitation. At present, most devices that can estimate paces and gaits are wearable and/or expensive. This paper presents an inexpensive, non-intrusive wireless binary sensor system for pace estimation and lower-extreme gait recognition with low data throughput and high energy efficiency. The asymmetric but periodic movement of injured person allows the study of pace and gait. The pace estimation is achieved by using autocorrelation function. The gait information is represented by three features (1) temporal correlation, (2) marginal density (intersection probability), and (3) spatial correlation from binary data steam. Experimental results shows that our system can estimate the pace of walking or running with the accuracy of 97.7%. By using only three features, abnormal gaits can also be recognized.