An independent set of variables is one in which no two variables occur in the same clause in a given instance of $k$-SAT. Instances of $k$-SAT with an independent set of size $i$ can be solved in time which is within a polynomial factor of $O(2^{n-i})$. In this paper we present an algorithm for $k$-SAT based on a modification of the Satisfiability Coding Lemma. Our algorithm runs within a polynomial factor of $2^{(n-i)(1-\frac{1}{2k-2})}$, where $i$ is the size of an independent set. We also present a variant of Schoening's randomized local-search algorithm for $k$-SAT that runs in time which is within a polynomial factor of $(\frac{2k-3}{k-1})^{n-i}$.